LeetCode 40 组合总和 II - 回溯解法
https://leetcode.cn/problems/combination-sum-ii/description/
思路
和 [子集2](LeetCode 90 子集 II - 回溯解法.md) 类似.
先排序， 重点在于如何去重.
举例: [0,1,1,2,3] target = 3; 对于第一个[1,2]是可以的， 但是第二个1开头就不应该加入到result中.
思路1
那么， 什么时候该跳过: 如果用candidate[i]==candate[i-1]来判断跳过,
第一个1没问题， 但是当path为[1]，for循环要遍历[1,2,3]时，这里的1就被跳过了，按道理不应该跳过， 如果1后面不是2是1 [1,1,2,3]那么第二个1应该被跳过， 因此被跳过的不能是第一个数.
思路2:
取第一个1后， 接着要遍历[1,2,3]. 取第二个1后要遍历[2,3]，这就重复了，所以重复是在一个for循环里， 也就是说你不可以和你兄弟相同，相同就必然会出现(组合)重复，你和你孩子相同会导致一个path中有重复元素，这是允许的， 可以设置一个变量 last初始为-1， 如果for循环取出的值等于last就应该跳过， 否则继续.
举例:
for(遍历全部){
0: 没事 -last =0;
第一个1: 没事 last = 1;
第二个1: 有事 跳掉因为他们的孩子树是相同的.
}
代码
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
vector<int> loc_canditates;
void sel_number(int start, int end, int sum, int target){
if(sum==target){
result.push_back(path);
return;
}
if(sum>target) return;
int last =-1;
for(int i = start;i<=end;i++){
//if(i>start&&loc_canditates[i]==loc_canditates[i-1])continue;
if(loc_canditates[i]==last) continue;
last = loc_canditates[i];
path.push_back(loc_canditates[i]);
sel_number(i+1,end,sum+loc_canditates[i],target);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
loc_canditates = candidates;
sort(loc_canditates.begin(),loc_canditates.end());
sel_number(0,candidates.size()-1, 0, target);
return result;
}
};