2022 年新一轮的打卡，准备每天都完成LeetCode的每日一题，并写下题解。今天的题目是698. Partition to k equal sum subsets
给定一个整数数组 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 时，则不可能划分。如果能整除，则 m = sum(nums) / k为每组的元素之和。
从提示来看，这个算法的复杂度估计很高，因为它给的输入范围就很小，数组元素个数最大才到16。
由于给的输入数据不大，所以可以考虑直接通过回溯暴力计算出来，是否能划分为k组。
解法 1：回溯法
回溯时可以先准备 k 个大小为 m 的桶，然后每次对数组中的一个元素，尝试将其放入某个桶中（需要保证桶内大小大于等于该元素大小），如果能把所有元素都放入桶内，则可以划分为 k 组。同时可以在进行回溯前对数组进行排序，然后按从大到小的顺序尝试将元素放入桶中。
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
| bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = 0;
for(auto i : nums) {
sum += i;
imap[i]++;
}
if (sum % k) return false;
int m = sum / k;
vector<int> buckets(k, m);
sort(nums.begin(), nums.end());
return dfs(nums, buckets, nums.size() - 1);
}
bool dfs(vector<int>& nums, vector<int>& buckets, int index) {
if (index < 0) return true;
for (int i = 0;i < buckets.size();i++) {
if (nums[index] <= buckets[i]) {
buckets[i] -= nums[index];
if (dfs(nums, buckets, index-1)) {
return true;
}
buckets[i] += nums[index];
}
}
return false;
}
|
上述算法还是没法直接AC的，需要加入各种剪枝条件。
解法2：回溯+剪枝
剪枝条件：
- 放入新的元素后，桶内剩余容积要大于最小元素大小：
buckets[i] - nums[index] > nums[0]
- 如果两个桶容积相同，则放哪个效果都一样，
buckets[i] == buckets[i - 1]
- 将要放入桶内的第 i 个元素，放在第 i - 1 个桶之后的哪个桶都是一样的，
nums.size() < i + index
加入剪枝条件后的代码：
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
| bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = 0;
unordered_map<int, int> imap;
for(auto i : nums) {
sum += i;
imap[i]++;
}
if (sum % k) return false;
int m = sum / k;
vector<int> buckets(k, m);
sort(nums.begin(), nums.end());
return dfs(nums, buckets, nums.size() - 1);
}
bool dfs(vector<int>& nums, vector<int>& buckets, int index) {
if (index < 0) return true;
for (int i = 0;i < buckets.size();i++) {
if (nums.size() < i + index) break;
if (i > 0 && buckets[i] == buckets[i - 1]) continue;
if (nums[index] == buckets[i] || buckets[i] - nums[index] >= nums[0]) {
buckets[i] -= nums[index];
if (dfs(nums, buckets, index-1)) {
return true;
}
buckets[i] += nums[index];
}
}
return false;
}
|
解法3 状态压缩 +动态规划
后续学习学习
官方题解