题目描述
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
- 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
- 输出： True
- 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
示例 2:
- 输入: nums = [1,2,3,4], k = 3
- 输出: false
- 提示：
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
每个元素的频率在 [1,4] 范围内
思路
首先，找到当前数组的总和能不能被k整除
- 能够被k整除的话，证明数组的数字总和能平均的分为k份
- 不能的话，就直接返回false
返回false的情况
- 当前数组的总和不能被k整除
- 数组中最大的值等于数组求和后的平均值
使用桶的思想解决：借用他人的观点如下：
以数组为[10,10,10,7,7,7,7,7,7,6,6,6]，分成3部分为例，
即分成3个桶，每个桶的和为30
排序后数组为[6,6,6,7,7,7,7,7,7,10,10,10]，需要放在3个桶中，每个桶的和为30
第一层递归，末尾的10放在第一个桶中
| | | | | |
| | | | | |
| | | | | |
|10 | | | | |
--- --- ---
桶1 桶2 桶3
第二层和第三层递归，倒数第二个和倒数第三个10都放在桶1中
| | | | | |
|10 | | | | |
|10 | | | | |
|10 | | | | |
--- --- ---
桶1 桶2 桶3
第四层递归，倒数第一个7就不能放在桶1中了，因为30+7>30
所以放在桶2中
| | | | | |
|10 | | | | |
|10 | | | | |
|10 | |7 | | |
--- --- ---
桶1 桶2 桶3
后续直到桶2中放了4个7，
| | |7 | | |
|10 | |7 | | |
|10 | |7 | | |
|10 | |7 | | |
--- --- ---
桶1 桶2 桶3
再有7就不能放到桶2中了，因为5*7>30
后续的2个7和2个6放到了桶3中
| | |7 | |6 |
|10 | |7 | |6 |
|10 | |7 | |7 |
|10 | |7 | |7 |
--- --- ---
桶1 桶2 桶3
这是第一个6这时没地方放了，因为放到任何一个桶中，都大于30
这时遍历3个桶，都没法放进去之后，返回false
然后递归返回，
递归返回到存放的倒数第二个6，倒数第二个6从桶3中出栈，但是没有桶4可以让倒数第二个6放进去了，
for循环直接结束了，同时返回false
同理，桶3中的元素会依次从桶3中出栈
然后桶2中的栈顶的7，会尝试放到桶3中，再递归下去，（剩余的数组元素为[6,6,6,7,7])
当然我们知道这种情况也是无解的，
| | | | | |
|10 | |7 | | |
|10 | |7 | | |
|10 | |7 | |7 |
--- --- ---
桶1 桶2 桶3
最终桶2中的元素，会全部依次出栈，此时数组中剩余的元素为[6,6,6,7,7,7,7,7,7]
| | | | | |
|10 | | | | |
|10 | | | | |
|10 | | | | |
--- --- ---
桶1 桶2 桶3
如果没有 if (groups[i] == 0) break; 这行代码
我们知道了桶2已经是空了，但是仍然会运行for循环，把倒数第一个位置的7，放到桶3中再次尝试，并继续递归下去
但是这样其实没有意义，因为桶2和桶3的地位是一样的，
这种情况也是无解的，所以可以剪枝
同样，桶1中的栈顶的2个10都会出栈，最终会平均分配到3个桶中，剩余的元素，也都会平均分配到每个桶中
|6 | |6 | |6 |
|7 | |7 | |7 |
|7 | |7 | |7 |
|10 | |10 | |10 |
--- --- ---
桶1 桶2 桶3
最后一次递归的时候 row就是-1了，这时直接返回true
代码
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
}
if(sum % k != 0){
return false;
}
//求出子集的和
sum = sum / k;
//排序 从小到大
Arrays.sort(nums);
//如果数组的最大值>target，证明有一个数是无法放入的，所以无法满足题意，直接返回false
if(nums[nums.length - 1] > sum){
return false;
}
//建立一个长度为k的桶
int[] arr = new int[k];
//将桶中的所有元素设置为子集的和，通过fill函数
Arrays.fill(arr, sum);
//从数组最后一个数开始进行递归
return help(nums, nums.length - 1, arr, k);
}
//cur：当前的元素位置
//arr：填满所求子集的和
//k：所要获取的子集数目
boolean help(int[] nums, int cur, int[] arr, int k){
//已经遍历到了-1说明前面的所有数都正好可以放入桶里，那所有桶的值此时都为0，说明找到了结果，返回true
if(cur < 0){
return true;
}
//遍历k个桶
for(int i = 0; i < k; i++){
//如果正好能放下当前的数，或者放下当前的数后，还有机会继续放前面的数（剪枝）
//arr[i] - nums[cur] >= nums[0]：条件成立是因为数组按从小到大排序，大于第一个就证明还可以继续存放数
if(arr[i] == nums[cur] || (cur > 0 && arr[i] - nums[cur] >= nums[0])){
//放当前的数到桶i里
arr[i] -= nums[cur];
//开始放下一个数
if(help(nums, cur - 1, arr, k)){
return true;
}
//这个数不该放在桶i中
//从桶中拿回当前的数
arr[i] += nums[cur];
}
}
return false;
}
}
代码说明
这次看注释吧，注释写的很清楚；
首先判断该数组所要求的子集是否能够出现，有两种情况不能出现：
- 当前数组的总和不能被k整除
- 数组中最大的值等于数组求和后的平均值
如果判断能够出现的话，就需要使用桶进行运算
- 遍历每一个桶
- 每一个桶能够存放的数据是之前所求的平均值
- 使用一个方法递归，