LeetCode 698 Partition to K Equal Sum Subsets
概述
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
回溯法（以数字的视角）
每次选择我们凑出一个满足要求的子集？但是好麻烦啊。
https://labuladong.gitee.io/algo/4/29/111/
这里给的思路是，维护 k 个桶，然后每个数字选择桶。
class Solution {
public:
int t;
int k;
bool canPartitionKSubsets(vector<int>& nums, int k) {
this->k = k;
int sum = 0;
for (auto& num : nums) sum += num;
if (sum % k != 0) return false;
t = sum / k;
vector<int> buckets(k, 0);
return backtrack(nums, buckets, 0);
}
bool backtrack(vector<int>& nums, vector<int>& buckets, int c) {
if (c == nums.size()) {
for (auto& b : buckets) {
if (b != t) return false;
}
return true;
}
for (auto& b : buckets) {
b += nums[c];
if (backtrack(nums, buckets, c + 1)) return true;
b -= nums[c];
}
return false;
}
};
TLE 了（37 / 159 test cases passed）。
加个小优化：if (b + nums[c] > t) continue;
又 TLE 了（54 / 159 test cases passed）。。
对数字降序排序，这样可以提早触发早停的 if 分支。
又又 TLE 了（151 / 159 test cases passed）。。。
回溯法（以桶的视角）
class Solution {
public:
int t;
int k;
bool canPartitionKSubsets(vector<int>& nums, int k) {
this->k = k;
int sum = 0;
for (auto& num : nums) sum += num;
if (sum % k != 0) return false;
t = sum / k;
vector<int> used(nums.size(), false);
sort(nums.begin(), nums.end());
return backtrack(nums, used, 0, 0);
}
bool backtrack(vector<int>& nums, vector<int>& used, int c, int idx) {
if (idx == k) {
return true;
}
for (int i = 0; i < nums.size(); i ++) {
if (used[i]) continue;
if (c + nums[i] > t) break;
used[i] = true;
if (c + nums[i] == t) {
if (backtrack(nums, used, 0, idx + 1)) return true;
} else {
if (backtrack(nums, used, c + nums[i], idx)) return true;
}
used[i] = false;
}
return false;
}
};
好家伙，又 TLE 了，给我整无语了属于是。
不玩了，花了好久了。