传送门
题目：给定一个整数数组 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循环）再去试。
