Massive Algorithms: LeetCode 698 - Partition to K Equal Sum Subsets

LeetCode 698 - Partition to K Equal Sum Subsets

Related: LeetCode 416 - Partition Equal Subset Sum
Partition of a set into K subsets with equal sum
Partition of a set into K subsets with equal sum + 3|K Partition Problem
LeetCode 698 - Partition to K Equal Sum Subsets
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

1 <= k <= len(nums) <= 16.

0 < nums[i] < 10000.

X. DP

http://www.cnblogs.com/grandyang/p/7733098.html

As in Approach #1, we investigate methods of exhaustive search, and find target = sum(nums) / k in the same way.

Let used have the i-th bit set if and only if nums[i] has already been used. Our goal is to use nums in some order so that placing them into groups in that order will be valid. search(used, ...) will answer the question: can we partition unused elements of nums[i] appropriately?

This will depend on todo, the sum of the remaining unused elements, not crossing multiples of target within one number. If for example our target is 10, and our elements to be placed in order are [6, 5, 5, 4], this would not work as 6 + 5 "crosses" 10 prematurely.

If we could choose the order, then after placing 5, our unused elements are [4, 5, 6]. Using 6 would make todo go from 15 to 9, which crosses 10 - something unwanted. However, we could use 5 since todogoes from 15 to 10; then later we could use 4 and 6 as those placements do not cross.

It turns out the maximum value that can be chosen so as to not cross a multiple of target, is targ = (todo - 1) % target + 1. This is essentially todo % target, plus target if that would be zero.

Now for each unused number that doesn't cross, we'll search on that state, and we'll return true if any of those searches are true.

Notice that the state todo depends only on the state used, so when memoizing our search, we only need to make lookups by used.

In the solutions below, we present both a top-down dynamic programming solution, and a bottom-up one. The bottom-up solution uses a different notion of state.

enum Result { TRUE, FALSE }

    boolean search(int used, int todo, Result[] memo, int[] nums, int target) {
        if (memo[used] == null) {
            memo[used] = Result.FALSE;
            int targ = (todo - 1) % target + 1;
            for (int i = 0; i < nums.length; i++) {
                if ((((used >> i) & 1) == 0) && nums[i] <= targ) {
                    if (search(used | (1<<i), todo - nums[i], memo, nums, target)) {
                        memo[used] = Result.TRUE;
                        break;
                    }
                }
            }
        }
        return memo[used] == Result.TRUE;
    }
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k > 0) return false;

        Result[] memo = new Result[1 << nums.length];
        memo[(1 << nums.length) - 1] = Result.TRUE;
        return search(0, sum, memo, nums, sum / k);
    }

Bottom-Up Variation

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int N = nums.length;
        Arrays.sort(nums);
        int sum = Arrays.stream(nums).sum();
        int target = sum / k;
        if (sum % k > 0 || nums[N - 1] > target) return false;

        boolean[] dp = new boolean[1 << N];
        dp[0] = true;
        int[] total = new int[1 << N];

        for (int state = 0; state < (1 << N); state++) {
            if (!dp[state]) continue;
            for (int i = 0; i < N; i++) {
                int future = state | (1 << i);
                if (state != future && !dp[future]) {
                    if (nums[i] <= target - (total[state] % target)) {
                        dp[future] = true;
                        total[future] = total[state] + nums[i];
                    } else {
                        break;
                    }
                }
            }
        }
        return dp[(1 << N) - 1];
    }

Time Complexity:

O(N * 2^N)

, where

N

is the length of nums. There are

2^N

states of used (or statein our bottom-up variant), and each state performs O(N) work searching through nums.

Space Complexity:

O(2^N)

, the space used by memo (or dp, total in our bottom-up variant).

X. DFS 2
https://www.youtube.com/watch?v=qpgqhp_9d1s
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108751/Easy-to-understand-java-solution
https://efficientcodeblog.wordpress.com/2017/12/01/partition-to-k-equal-sum-subsets/

Time Complexity: $O(k^{N-k} k!)$ , where $N$ is the length of nums, and $k$ is as given. As we skip additional zeroes in groups, naively we will make $O(k!)$ calls to search, then an additional $O(k^{N-k})$ calls after every element of groups is nonzero.
Space Complexity: $O(N)$ , the space used by recursive calls to search in our call stack.

Firstly, we know that each of the k group-sums must be equal to target = sum(nums) / k. (If this quantity is not an integer, the task is impossible.) For each number in nums, we could add it into one of k group-sums, as long as the group’s sum would not exceed the target. For each of these choices, we recursively search with one less number to consider in nums. If we placed every number successfully, then our search was successful. One important speedup is that we can ensure all the 0 values of each group occur at the end of the array groups, by enforcing if (groups[i] == 0) break;. This greatly reduces repeated work – for example, in the first run of search, we will make only 1 recursive call, instead of k. Actually, we could do better by skipping any repeated values of groups[i], but it isn’t necessary. Another speedup is we could sort the array nums, so that we try to place the largest elements first. When the answer is true and involves subsets with a low size, this method of placing elements will consider these lower size subsets sooner. We can also handle elements nums[i] >= target appropriately. These tricks are not necessary to solve the problem, but they are presented in the solutions below.

https://www.jianshu.com/p/11970b02ba01

后来发现换一种思路就好做很多。假设题目改成从一个数组中选择若干个数字使其和为target，那么对于每个元素来说，都有选中和不选中两种决定，那么简单的DFS就可以解决。
扩展到这道题目来说，其实就是将上面的DFS换成一个数组group[]，group[i]代表第i个subset。对于每个nums[j]，在每个group中都有出现和不出现两种可能。
值得一提的是，需要提前做剪枝，排除掉没有解的情况，这样在填充group[]的过程中保证一定有解，这样只要处理到了最后一个（或者逆向的最后一个）元素之后，就知道找到解了，就可以返回true。否则还需要额外判断group[]中每个元素是否等于target。

public boolean canPartitionKSubsets(int[] nums, int k) {

int sum = 0;

for (int n : nums) {

sum += n;

}

if (sum % k != 0) {

return false;

}

int target = sum / k;

Arrays.sort(nums);

if (nums[nums.length - 1] > target) {

return false;

}

int row = nums.length - 1;

while (row >= 0 && nums[row] == target) {

--row;

--k;

}

return search(new int[k], row, nums, target);

}

public boolean search(int[] groups, int row, int[] nums, int target) {

if (row < 0) {

return true;

}

int v = nums[row--];

for (int i = 0; i < groups.length; ++i) {

if (groups[i] + v <= target) {

groups[i] += v;

if (search(groups, row, nums, target)) {

return true;

}

groups[i] -= v;

}

if (groups[i] == 0) {

// fill groups[i] ahead of groups[i + 1]

break;

}

return false;

}

下面这种方法也挺巧妙的，思路是建立长度为k的数组v，只有当v里面所有的数字都是target的时候，才能返回true。我们还需要给数组排个序，由于题目中限制了全是正数，所以数字累加只会增大不会减小，一旦累加超过了target，这个子集合是无法再变小的，所以就不能加入这个数。实际上相当于贪婪算法，由于题目中数组数字为正的限制，有解的话就可以用贪婪算法得到。我们用一个变量idx表示当前遍历的数字，排序后，我们从末尾大的数字开始累加，我们遍历数组v，当前位置加上nums[idx]，如果超过了target，我们掉过继续到下一个位置，否则就调用递归，此时的idx为idx-1，表示之前那个数字已经成功加入数组v了，我们尝试着加下一个数字。如果递归返回false了，我们就将nums[idx]从数组v中对应的位置减去，还原状态，然后继续下一个位置。如果某个递归中idx等于-1了，表明所有的数字已经遍历完了，此时我们检查数组v中k个数字是否都为target，是的话返回true，否则返回false

https://shineboy2013.github.io/2018/01/28/lee-698/
另一个方法是，将k次排列组合法整合成一次，途径是开一个k大小数组，每一个数肯定属于其中一个。visited数组替换成ksum数组和idx控制遍历数组顺序。某一个数肯定是属于ksum数组的任一个，

所以所有可能性都考虑到，可以求得解。先对原数组排序，贪心算法可以帮助剪枝，提高算法效率但若不排序的话会得到LTE。

public boolean canPartitionKSubsets(int[] nums, int k) {
 int sum = 0;
 for(int i : nums)
  sum+=i;
 if(sum%k!=0)
  return false;
 Arrays.sort(nums);
 int[] ksum = new int[k];
 return dfs(nums, k, sum/k, ksum, nums.length-1);
}

public boolean dfs(int[] nums, int k, int target, int[] ksum, int idx){
 if(idx==-1){
  for(int a : ksum)
   if(a!=target)
    return false;
  return true;
 }
 for(int i=0; i<k; i++){
  if(ksum[i]+nums[idx]<=target){
   ksum[i] += nums[idx];
   if(dfs(nums, k, target, ksum, idx-1))
    return true;
   ksum[i] -= nums[idx];
  }
  
 }
 return false;
}

X. DFS
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/180014/Thinking-Process-of-Recursion-in-Java

canPartitionKSubsets() is true if there are exactly k subsets sum up to sum / k for each element can only be used once.

k restricts there are k combinations exactly
comparison between curSubsetSum and targetSubsetSum indicates whether we find a valid subset.

We can take it as a two-layer recursion.

Outer recursion:
Base case: k == 0
Recursive case: // Inner recursion
    Base case: curSubsetSum > targetSubsetSum 
    Recursive case: curSubsetSum == targetSubsetSum (decrease k by 1)
                    curSubsetSum < targetSubsetSum

Since the order of numbers within a subset doesn't matter, we add innerStart for the enumeration to construct a subset in order to avoid duplicate calculations.

    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (k == 1) return true;
        
        int totalSum = 0, maxNum = Integer.MIN_VALUE;
        for (int num : nums) {
            totalSum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (totalSum % k != 0) return false;
        int targetSubsetSum = totalSum / k;
        if (maxNum > targetSubsetSum) return false;
        
        return canPartitionAfter(nums, k, targetSubsetSum, 0, new boolean[nums.length], 0);
    }
    
    private boolean canPartitionAfter(int[] nums, int k, int targetSubsetSum, int curSubsetSum, boolean[] visited, int innerStart) {
        if (0 == k) return true; // Outer base case.
        if (curSubsetSum > targetSubsetSum) return false; // Inner base case.

        if (curSubsetSum == targetSubsetSum) return canPartitionAfter(nums, k - 1, targetSubsetSum, 0, visited, 0); // Enter a new subset.
        
        // Enumerate numbers in a subset.
        for (int i = innerStart; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                if (canPartitionAfter(nums, k, targetSubsetSum, curSubsetSum + nums[i], visited, i + 1)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        
        return false;
    }

这道题给了我们一个数组nums和一个数字k，问我们该数字能不能分成k个非空子集合，使得每个子集合的和相同。给了k的范围是[1,16]，而且数组中的数字都是正数。这跟之前那道 Partition Equal Subset Sum 很类似，但是那道题只让分成两个子集合，所以问题可以转换为是否存在和为整个数组和的一半的子集合，可以用dp来做。但是这道题让求k个和相同的，感觉无法用dp来做，因为就算找出了一个，其余的也需要验证。这道题我们可以用递归来做，首先我们还是求出数组的所有数字之和sum，首先判断sum是否能整除k，不能整除的话直接返回false。然后需要一个visited数组来记录哪些数组已经被选中了，然后调用递归函数，我们的目标是组k个子集合，是的每个子集合之和为target = sum/k。我们还需要变量start，表示从数组的某个位置开始查找，curSum为当前子集合之和，在递归函数中，如果k=1，说明此时只需要组一个子集合，那么当前的就是了，直接返回true。如果curSum等于target了，那么我们再次调用递归，此时传入k-1，start和curSum都重置为0，因为我们当前又找到了一个和为target的子集合，要开始继续找下一个。否则的话就从start开始遍历数组，如果当前数字已经访问过了则直接跳过，否则标记为已访问。然后调用递归函数，k保持不变，因为还在累加当前的子集合，start传入i+1，curSum传入curSum+nums[i]，因为要累加当前的数字，如果递归函数返回true了，则直接返回true。否则就将当前数字重置为未访问的状态继续遍历

我们也可以对上面的解法进行一些优化，比如先给数组按从大到小的顺序排个序，然后在递归函数中，我们可以直接判断，如果curSum大于target了，直接返回false，因为题目中限定了都是正数，并且我们也给数组排序了，后面的数字只能更大，这个剪枝操作大大的提高了运行速度

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false;
        sort(nums.begin(), nums.end(), greater<int>());
        vector<bool> visited(nums.size(), false);
        return helper(nums, k, sum / k, 0, 0, visited);
    }
    bool helper(vector<int>& nums, int k, int target, int start, int curSum, vector<bool>& visited) {
        if (k == 1) return true;
        if (curSum > target) return false;
        if (curSum == target) return helper(nums, k - 1, target, 0, 0, visited);  
        for (int i = start; i < nums.size(); ++i) {
            if (visited[i]) continue;
            visited[i] = true;
            if (helper(nums, k, target, i + 1, curSum + nums[i], visited)) return true;
            visited[i] = false;
        }
        return false;
    }

As even when k = 2, the problem is a "Subset Sum" problem which is known to be NP-hard, (and because the given input limits are low,) our solution will focus on exhaustive search.

A natural approach is to simulate the k groups (disjoint subsets of nums). For each number in nums, we'll check whether putting it in the i-th group solves the problem. We can check those possibilities by recursively searching.

Firstly, we know that each of the k group-sums must be equal to target = sum(nums) / k. (If this quantity is not an integer, the task is impossible.)

For each number in nums, we could add it into one of k group-sums, as long as the group's sum would not exceed the target. For each of these choices, we recursively search with one less number to consider in nums. If we placed every number successfully, then our search was successful.

One important speedup is that we can ensure all the 0 values of each group occur at the end of the array groups, by enforcing if (groups[i] == 0) break;. This greatly reduces repeated work - for example, in the first run of search, we will make only 1 recursive call, instead of k. Actually, we could do better by skipping any repeated values of groups[i], but it isn't necessary.

Another speedup is we could sort the array nums, so that we try to place the largest elements first. When the answer is true and involves subsets with a low size, this method of placing elements will consider these lower size subsets sooner. We can also handle elements nums[i] >= target appropriately. These tricks are not necessary to solve the problem, but they are presented in the solutions below.

Time Complexity: $O(k^{N-k} k!)$ , where $N$ is the length of nums, and $k$ is as given. As we skip additional zeroes in groups, naively we will make $O(k!)$ calls to search, then an additional $O(k^{N-k})$ calls after every element of groups is nonzero.
Space Complexity: $O(N)$ , the space used by recursive calls to search in our call stack.

    public boolean search(int[] groups, int row, int[] nums, int target) {
        if (row < 0) return true;
        int v = nums[row--];
        for (int i = 0; i < groups.length; i++) {
            if (groups[i] + v <= target) {
                groups[i] += v;
                if (search(groups, row, nums, target)) return true;
                groups[i] -= v;
            }
            if (groups[i] == 0) break;
        }
        return false;
    }

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k > 0) return false;
        int target = sum / k;

        Arrays.sort(nums);
        int row = nums.length - 1;
        if (nums[row] > target) return false;
        while (row >= 0 && nums[row] == target) {
            row--;
            k--;
        }
        return search(new int[k], row, nums, target);
    }

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108730/JavaC++Straightforward-dfs-solution

Assume sum is the sum of nums[] . The dfs process is to find a subset of nums[] which sum equals to sum/k. We use an array visited[] to record which element in nums[] is used. Each time when we get a cur_sum = sum/k, we will start from position 0 in nums[] to look up the elements that are not used yet and find another cur_sum = sum/k.

An corner case is when sum = 0, my method is to use cur_num to record the number of elements in the current subset. Only if cur_sum = sum/k && cur_num >0, we can start another look up process.

Some test cases may need to be added in:
nums = {-1,1,0,0}, k = 4
nums = {-1,1}, k = 1
nums = {-1,1}, k = 2
nums = {-1,1,0}, k = 2

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(int num:nums)sum += num;
        if(k <= 0 || sum%k != 0)return false;
        int[] visited = new int[nums.length];
        return canPartition(nums, visited, 0, k, 0, 0, sum/k);
    }
    
    public boolean canPartition(int[] nums, int[] visited, int start_index, int k, int cur_sum, int cur_num, int target){
        if(k==1)return true;
        if(cur_sum == target && cur_num>0)return canPartition(nums, visited, 0, k-1, 0, 0, target);
        for(int i = start_index; i<nums.length; i++){
            if(visited[i] == 0){
                visited[i] = 1;
                if(canPartition(nums, visited, i+1, k, cur_sum + nums[i], cur_num++, target))return true;
                visited[i] = 0;
            }
        }
        return false;
    }

We don't need to track number of elements

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int S = 0;
        int n = nums.size();
        for (int e:nums)
            S += e;
        if (S%k != 0)
            return false;
        S = S/k;
        vector<bool> visited(n, false);
        return canPartition(nums,visited, k, 0, 0, S);
    }
    
    bool canPartition(vector<int>& nums, vector<bool>& visited, int k, int start, int s, int S) {
        if (k == 1)
            return true;
        if (s == S)
            return canPartition(nums, visited, k-1, 0, 0, S);
        for (int i = start; i < nums.size(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                if (canPartition(nums,visited, k, i+1, s+nums[i], S))
                    return true;
                visited[i] = false;
            }
        }
        return false;
    }

https://zxi.mytechroad.com/blog/searching/leetcode-698-partition-to-k-equal-sum-subsets/
Time complexity: O(n!)

  bool canPartitionKSubsets(vector<int>& nums, int k) {

    const int sum = accumulate(nums.begin(), nums.end(), 0);

    if (sum % k != 0) return false;    

    sort(nums.rbegin(), nums.rend());    

    return dfs(nums, sum / k, 0, k, 0);

}

private:

  bool dfs(const vector<int>& nums, int target, int cur, int k, int used) {

    if (k == 0) return used == (1 << nums.size()) - 1;

    for (int i = 0; i < nums.size(); ++i) {

      if (used & (1 << i)) continue;

      int t = cur + nums[i];

      if (t > target) break; // Important

      int new_used = used | (1 << i);

      if (t == target && dfs(nums, target, 0, k - 1, new_used)) return true; 

      else if (dfs(nums, target, t, k, new_used)) return true;

}

    return false;

}

https://www.geeksforgeeks.org/partition-set-k-subsets-equal-sum/

https://blog.csdn.net/jack_cjz/article/details/78571215
题目中限定了0 < nums[i] < 10000，当 nums[i] 中存在负数时，需要对代码进行一定的改动：

计算当前递归层的子集时，如果加入的数使得当前子集的和超过了 target ，此时不能直接 return false ，因为后面可能加入负数后可以使得当前子集的和等于 target 。
当 target == sum / k == 0 时，注意到空集的和也是 0 ，此时要加入一个计数器 elemNum 计算当前子集的元素个数，防止出现空集。
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = 0;
for (int i = 0; i < nums.size(); ++i) { sum += nums[i]; }
if (sum % k != 0) { return false; }

vector<bool> visited(nums.size(), false);
return canPartition(nums, visited, 0, 0, 0, k, sum / k);
}

// startIndex 表示从第几个位置开始选后面的数加入当前子集中
// curSum 表示当前子集的所有元素的和
// elemNum 表示当前子集的元素个数
// k 为剩下的子集数
bool canPartition(vector<int>& nums, vector<bool>& visited,
int startIndex, int curSum, int elemNum, int k, int target) {
if (k == 1) { return true; }
if (curSum == target && elemNum > 0) {
return canPartition(nums, visited, 0, 0, 0, k - 1, target);
}

for (int i = startIndex; i < nums.size(); ++i) {
if (!visited[i]) {
visited[i] = true;
if (canPartition(nums, visited, i + 1, curSum + nums[i], elemNum + 1, k, target)) {
return true;
}
visited[i] = false;
}
}

return false;
}

LeetCode 698 - Partition to K Equal Sum Subsets

Labels

Popular Posts