40. 组合总和 II

给定一个候选人编号的集合 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:
    vectorint>>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];
            }
        }
    }
    vectorint>> combinationSum2(vector<int>& candidates, int target) {
        //组合不能重复，但是如果有多个位置的元素值相同，则组合内元素值可以相同
        sort(candidates.begin(),candidates.end());
        backtracking(candidates,target,0);
        return res;
    }
};

 2、利用used数组，标记。

引入两个名词->两个维度上的去重

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]使用过

class Solution {
public:
    vectorint>>res;
    vector<int>path;
    //unordered_map,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;
        }
    }
    vectorint>> combinationSum2(vector<int>& candidates, int target) {
        //为了去重，得排序
        sort(candidates.begin(),candidates.end());
        vector<bool>used(candidates.size(),false);
        backtracking(candidates,target,0,used);
 
        return res;
    }
};