题目描述
一道枚举方案数的题,和算法提高课的枚举互质数很像,涉及知识点为DFS+剪枝
剪枝有:
优化搜索顺序:先对数组按照从大到小排序,减少搜索分支
可行性剪枝:若当前组内数大于target,返回
排除等效冗余:在同一组内,从start开始搜。当开了新的一组后,从0开始搜。这种方法搜出来的方案每组是按照组合而不是排列。
C++ 代码
class Solution {
public:
int n;
bool canPartitionKSubsets(vector<int>& nums, int k) {
int sum = accumulate(nums.begin(), nums.end(),0);
if(sum % k != 0) return false;
n = nums.size();
sort(nums.rbegin(),nums.rend());
vector<bool> st(n,false);
return dfs(nums, k, sum/k, 0, 0, st);
}
bool dfs(vector<int>&nums, int k, int target, int start, int cursum,
vector<bool> &st)
{
if(k == 1) return true;
if(cursum > target) return false;
if(cursum == target) return dfs(nums, k-1, target, 0, 0, st);
for(int i = start; i < n; i++)
{
if(st[i]) continue;
st[i] = true;
if (dfs(nums, k, target, i + 1, cursum + nums[i], st)) return true;
st[i] = false;
}
return false;
}
};