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.

Solution

DFS

乍一看这道题，感觉很难，因为完全不知道该怎么组合啊，怎么从array中选出几个数使其和为target呢？

后来发现换一种思路就好做很多。假设题目改成从一个数组中选择若干个数字使其和为target，那么对于每个元素来说，都有选中和不选中两种决定，那么简单的DFS就可以解决。

扩展到这道题目来说，其实就是将上面的DFS换成一个数组group[]，group[i]代表第i个subset。对于每个nums[j]，在每个group中都有出现和不出现两种可能。

值得一提的是，需要提前做剪枝，排除掉没有解的情况，这样在填充group[]的过程中保证一定有解，这样只要处理到了最后一个（或者逆向的最后一个）元素之后，就知道找到解了，就可以返回true。否则还需要额外判断group[]中每个元素是否等于target。

class Solution {
    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;
    }
}

DP

TBD