题目简介：
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
1
2
3
| 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
|
示例 2:
1
2
| 输入: nums = [1,2,3,4], k = 3
输出: false
|
提示：
1 <= k <= len(nums) <= 160 < nums[i] < 10000- 每个元素的频率在
[1,4] 范围内
思路：
利用回溯，使用球视角，即让球去选择桶。
每次回溯让当前的球去寻找合适的桶，若所有球都已分配完毕，则说明完成了k个子集的划分。
tips:
- 将数组降序排序，减小时间消耗（让桶最快的到达
target）
- 若两个桶的状态相同，则无论
nums[i]加入哪个桶，结果都是一样的，可以剪枝
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
bool solve(int target, vector<int>& bucket, int idx, vector<int>& nums){
if(idx == nums.size())
return true;
for(int i = 0; i < bucket.size(); i++){
if(nums[idx] + bucket[i] > target)
continue;
if(i > 0 && bucket[i] == bucket[i - 1])
continue;
bucket[i] += nums[idx];
if(solve(target, bucket, idx + 1, nums))
return true;
bucket[i] -= nums[idx];
}
return false;
}
bool canPartitionKSubsets(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater<int>());
int sum = accumulate(nums.begin(), nums.end(), 0);
int target = sum / k;
vector<int> bucket(k, 0);
return solve(target, bucket, 0, nums);
}
};
|
