698.partitiontokequalsumsubsets划为k个相等的子集

问题描述

698.划为k个相等的子集

解题思路

首先，对数组按照从大到小排序，相比从小到大排序，能避免[1, 1, 2, 2]这样的数组的误判;

利用used[i]数组避免重复使用同一个元素，如果sum == target，就将sum置零，如果cnt == k，说明满足条件。

代码

class Solution {
public:
bool dfs(vector &nums, int index, int sum, int target, int cnt, int k, vector &used, int idx) {
if (cnt == k)
return true;
if (sum == target) {
return dfs(nums, idx - 1, 0, target, cnt + 1, k, used, idx - 1); //注意这里是idex - 1而不是index - 1
}
for (int i = index; i >= 0; i--) {
if (used[i] || sum + nums[i] > target)
continue;
used[i] = 1;
if (dfs(nums, i - 1, sum + nums[i], target, cnt, k, used, idx))
return true;
used[i] = 0;
if (sum == 0)
return false;
}
return false;
}
bool canPartitionKSubsets(vector &nums, int k) {
int sum = 0;
for (int i : nums)
sum += i;
if (sum % k != 0)
return false;
std::sort(nums.begin(), nums.end());
if (nums.back() > sum / k)
return false;
vector used(nums.size(), 0);
return dfs(nums, nums.size() - 1, 0, sum / k, 0, k, used, nums.size() - 1);
}
};