给定一个候选人编号的集合 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5]
, target =8
, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
1、利用startindex进行去重
class Solution {
public:
vector<vector<int>>res;
vector<int>path;
int sum = 0;
void backtracking(vector<int>& candidates, int target,int startindex){
if(sum > target) return;
if(sum == target){
res.push_back(path);
return;
}
for(int i = startindex;i < candidates.size();i++){
//1 1 2
//去重逻辑,就是排序后的木匾数组,在树层遍历(横向遍历)时前一个不能和后一个相等。
//前一个比后一个的1早,且范围大,第二个1往后遍历的结果,都是第一个1遍历后的子集,即,第一个1早就遍历过了。第二个1再遍历,就会产生重复组合。
if(i > startindex && candidates[i] == candidates[i-1]){
//i > startindex,说明当前是在遍历一个树层,横向遍历,startindex不变,i++。
//i==startindex,说明在一层中选中一个值以后,往下遍历,这一层的i不变,index++.
continue;
}
else{
path.push_back(candidates[i]);
sum += candidates[i];
backtracking(candidates,target,i+1);
path.pop_back();
sum -= candidates[i];
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
//组合不能重复,但是如果有多个位置的元素值相同,则组合内元素值可以相同
sort(candidates.begin(),candidates.end());
backtracking(candidates,target,0);
return res;
}
};
2、利用used数组,标记。
引入两个名词->两个维度上的去重文章来源:https://www.toymoban.com/news/detail-726462.html
1、树枝去重:比如(1,1,2),向下递归的时候,如果开始用第二个1,发现第一个1用过了,就continue了,会漏掉112,这个结果(题目不允许重复使用一个位置上的相同元素) used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
2、树层去重:(1,1,2),想右遍历的时候,如果遍历到第二个1,发现第一个1使用过(但是used是false,是由于递归回溯的时候,又初始化了),又因为是排过序的,所以第二个1之后遍历到的结果,肯定已经被第一个1包含了,即再取就重复了。 used[i - 1] == false,说明同一树层candidates[i - 1]使用过文章来源地址https://www.toymoban.com/news/detail-726462.html
class Solution {
public:
vector<vector<int>>res;
vector<int>path;
//unordered_map<vector<int>,int>map;
int sum = 0;
void backtracking(vector<int>& candidates, int target,int startindex,vector<bool>& used){
//终止条件
if(sum > target) return;
if(sum == target){
//最开始想用map或者set去重,但是错误不断
//sort(path.begin(),path.end());
//map[path]++;
//if(map[path] > 1) return;// 出现了两次
//else res.push_back(path);
res.push_back(path);
return;
}
for(int i = startindex;i < candidates.size();i++){
//去重
if(i>0 && candidates[i] == candidates[i-1] && !used[candidates[i-1]]){
continue;
}
path.push_back(candidates[i]);
sum += candidates[i];
used[candidates[i]] = true;
backtracking(candidates,target,i+1,used);
path.pop_back();
sum -= candidates[i];
used[candidates[i]] = false;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
//为了去重,得排序
sort(candidates.begin(),candidates.end());
vector<bool>used(candidates.size(),false);
backtracking(candidates,target,0,used);
return res;
}
};
到了这里,关于40. 组合总和 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!