@Leetcode
这题与Leetcode 39 Combination Sum(组合总和)的区别是:
- 本题candidates里面的元素每个只能使用一次
- 本题candidates里的元素有重复, 而Leetcode 39 Combination Sum(组合总和)里candidates元素不重复.
难点:集合有重复元素,但还不能有重复的组合。
解决:组合问题为树形结构,“使用过某个元素”在树型结构上有两个维度,一个维度是同一树枝上使用过,另一个是同一层使用过。
题目要求的是组合不能重复,而组合内的元素可以重复。故我们要去重的同一树层的“使用过”
。(使用vector<bool> used数组)
注意:树层去重的话,需要对数组排序!
回溯三步曲
- 递归函数参数
vector<bool> used;
void generateSum(vector<int>& candidates, int target, int startIndex, int &sum, vector<int> &p)
- 递归终止条件
if(sum == target){
res.push_back(p);
return;
}
- 单层搜索过程
在candidates[i] == candidates[i-1]的情况下:
used[i-1] = true, 说明同一`树枝`candidates[i-1]使用过。
used[i-1] = false, 说明同一`树层`candidates[i-1]使用过。
// 同一树层上去重
if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false)
continue;
for(int i = start; i < candidates.size() && sum + candidates[i] <= target; i++){
if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false)
continue;
p.push_back(candidates[i]);
sum = sum + candidates[i];
used[i] = true;
generateSum(candidates, target, i+1, sum, p);//不用i+1了,表示可以取重复的数(与combination的区别之处)
sum = sum - candidates[i];
p.pop_back();
used[i] = false;
}
全部代码:
class Solution {
private:
int sum = 0;
vector<vector<int>> res;
vector<bool> used;
void generateSum(vector<int>& candidates, int target, int start, int &sum, vector<int> &p){
if(sum == target){
res.push_back(p);
//cout<<p[0]<<":"<<endl;
//for(int i = 0; i < p.size(); i++)
//cout<<p[i];
cout<<endl;
//cout<<"return1"<<endl;
return;
}
if(sum > target)
return;
for(int i = start; i < candidates.size() && sum + candidates[i] <= target; i++){
if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false)
continue;
p.push_back(candidates[i]);
sum = sum + candidates[i];
used[i] = true;
generateSum(candidates, target, i+1, sum, p);//不用i+1了,表示可以取重复的数(与combination的区别之处)
sum = sum - candidates[i];
p.pop_back();
used[i] = false;
//else
//return;
}
return;
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
res.clear();
vector<int> p;
sort(candidates.begin(), candidates.end()); //排序,让相同的元素挨在一起
used = vector<bool>(candidates.size(), false);
generateSum(candidates, target, 0, sum, p);
return res;
}
};