0回溯中等 LeetCode698. 划分为k个相等的子集

698. 划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

回溯的思想：递归遍历数组nums，把nums中的数值填充buckets的每个元素，使其都等于target。

k个子集理解为k个桶，用一个长度是k的数组buckets表示。

剪枝：

• 一个nums的元素有k种选择，选择插入后和不会超过target的桶插入，然后递归考虑下一个nums的元素。
• 给数组nums排序，优先考虑值更大的元素。
• 用nums的总和sum除以k看能否整除。target = sum / k

回溯的结束条件：
当递归深度已经到达nums的长度时，说明每个nums的元素都插入到桶中了。
理由：因为只有插入之后和不会超过target才能插入，每个元素都能插入到桶中说明没有哪个桶是超过target的，又因为nums的元素已经用光了，所以每个桶的大小只能是target才能满足上述情况，否则一定有一个桶会超过target，那样的话就nums的元素就不会全部被插入，直接返回false。

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int[] buckets = new int[k];
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % k != 0)  {
            return false;
        }
        int target = sum / k;
        Arrays.sort(nums);
        if (nums[nums.length-1] > target) {
            return false;
        }
        return backTrace(nums,nums.length-1,buckets,target);
    }

    public boolean backTrace(int[] nums, int cur, int[] buckets, int target) {
        if (cur < 0) {
            return true;
        }
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] + nums[cur] > target) {
                continue;
            }
            if (i > 0 && buckets[i] == buckets[i-1]) {
                continue;
            }
            buckets[i] += nums[cur];
            if (backTrace(nums,cur-1,buckets,target)) {
                return true;
            }
            buckets[i] -= nums[cur];
        }
        return false;
    }
}