博客

传送门

题目

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


输入

： nums = [4, 3, 2, 3, 5, 2, 1], k = 4

输出

： True


说明

： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

这种找子集的题，先求和，然后除以子集个数，得到每一部分的子集和，然后凑子集和

    int[] bucket; // 放k的子集的和
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (k == 1) return true; //如果k是1，直接返回true。
        int len = nums.length;
        int sum = 0;
        for (int num : nums) sum += num; // 算出nums的总和。
        if (sum % k != 0) return false; //子集分不出k份，直接false。
        sum /= k;// sum变为每个子集的和。
        Arrays.sort(nums);
        // Arrays.sort(nums, (a, b)->(b - a));//这样降序失败，因为nums里是基本类型int
        /*
            为什么要排序呢，其实不排序这道题也能做对，但是由于时间的关系就t了。
            排序就是为了优化时间，怎么优化呢？
            我们从nums中最大的数开始找，如果最大的数比子集和都要大，
            或者装下它后没到子集和的大小但是装不下nums中最小的值了，
            那么这个nums绝对是false，因为有一个这么大的数在nums里，
            你把它放在哪个子集里都不合适。
        */
        bucket = new int[k];//这个数组里放的是子集和，总共有k个。
    	Arrays.fill(bucket, sum);
        return dfs(k, nums, len - 1);
    }

    public boolean dfs(int k, int[] nums, int cur) {//cur为当前的位置，从最后开始往前走。
        if (cur < 0) return true;// cur走到-1时，说明所有的数全部都放进桶里了。这时一定是true
        for (int i = 0; i < k; i++) {
            //两种可能，这个数正好是桶当前的容量，或者将这个数放进桶后这个桶还能再放别的数。
            // if里也可以写成bucket[i]>=nums[cur] 但是起不到减枝的效果了
            if (bucket[i] == nums[cur] || bucket[i] - nums[cur] >= nums[0]) {
                bucket[i] -= nums[cur];
                if (dfs(k, nums, cur - 1)) return true;
                bucket[i] += nums[cur];//回溯
            }
        }
        return false;
	}

这里讨论一种问题，为什么只要判断cur<0就能说明true，而不需要判断一下bucket数组中的值是否都是0。

有没有可能bucket数组中的数有剩余但是cur已经小于0了呢？

答案是不可能

。

因为如果cur<0,那么说明nums中的所有数全部都放进去了。

cur一旦有一个递归没下去cur就不可能为-1，只能换其他的情况（下一次for循环）再去试。