一:题目
二:上码
class Solution {
public:
/**
思路:1.题目中说的每个数字只在每个组合中使用一次的话 我们可以考虑 在递归遍历的时候 index+1
不断缩小范围(因为这也是在一个大的集合中挑选小的集合,所以是需要记录index的)
2.但是我们在填写的时候需要注意的是我们需要控制横向的数字是否会出现重复,因为我们在
记录一条路径的时候,如果横向的遍历数字中出现重复的数字,那么必然出现重复的
组合
*/
vector<vector<int> >ans;
vector<int>path;
void backstacking(vector<int>&v,int num,int index) {
int sum = accumulate(path.begin(),path.end(),0);
if(sum > num) {
return ;
}
if(sum == num) {
ans.push_back(path);
return ;
}
for(int i = index; i < v.size(); i++) {
if(i > index && v[i] == v[i-1]) continue;//这里我们是将排序后的元素如果出现重复的就会
//跳过
path.push_back(v[i]);
backstacking(v,num,i+1);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
//这里我们需要注意的是我们将其排序是为了防止出现重复的组合
//这里我们可以知道的是 当我们横向遍历的时候如果出现相同的元素那么我们就需要跳过
//否则就会出现相同的元素。
sort(candidates.begin(),candidates.end());
backstacking(candidates,target,0);
return ans;
}
};