(Leetcode; Dynamic Programming) Partition to K Equal Sum Subsets memoization

Question

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

This is leetcode problem #698.

Below is code that I have written with backtracking to solve the problem (it is correct and passes all test cases).

When we apply memoization for a DP solution shouldn't the current state we are in for memoization depend on all of: currSum, count, and taken? Instead, all we need is taken and not currSum and count to uniquely identify our state.

For clarification: taken tells us which numbers we've selected thus far (or havent selected), count tells us the number of subsets we've currently divided into subsets, and currSum tells us the current sum for the subset we're trying to solve.

So why do we only need taken to identify the memoization state, and not all of taken and count and currSum?

class Solution {
    bool helper(const vector<int>& nums, int k, int count, int currSum, int targetSum, int index, vector<int>& taken) {
        if (count == k - 1)
            return true;
        
        if (currSum > targetSum)
            return false;
        
        if (currSum == targetSum)
            return helper(nums, k, count + 1, 0, targetSum, 0, taken);
        
        for (int i = index; i < nums.size(); i++) {
            if (!taken[i]) {
                taken[i] = 1;
                if (helper(nums, k, count, currSum + nums[i], targetSum, i + 1, taken))
                    return true;
                taken[i] = 0;
            }
        }
        
        return false;
    }
    
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), greater<>());
        vector<int> taken(nums.size(), 0);
        
        const int sum = accumulate(nums.begin(), nums.end(), 0);
        
        if (sum % k != 0 || *max_element(nums.begin(), nums.end()) > sum / k)
            return false;             
        
        return k == 1 || helper(nums, k, 0, 0, sum / k, 0, taken);
    }
};

Answer 1

Here is the signature of the recursive method,

bool helper(const vector<int>& nums, int k, int count, int currSum, int targetSum, int index, vector<int>& taken);

That means a state is implemented as a collection of 7 items, nums, k, count, currSum, targetSum, index, taken.

---

However, a state is completely determined by nums, k and taken. Once they are known, other items, targetSum, currSum, and index are determined.

• targetSum is the sum of all elements in nums divided by k.
• count is the integer quotient of the sum of all elements taken except the element taken at the largest index divided by targetSum.
• currSum is the sum of all elements taken minus the product of count and targetSum.
• index is $0$ if no element has been taken or one more than the largest index at which an element is taken.

Since nums and k are constants, we can also view a state as completely determined by taken, once the input vector<int>& nums, int k is given. That is why we only need taken to identify the state.

Given the constants nums and k, in math terms, we can view a state as having one independent variable taken and other dependent variables. In database terms, the table of all states has one primary key taken and other non-key columns.