题目：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]

]

整体思路

大的框架就是回溯搜索，这里首先要注意搜索时同一个结果中不能包含同样的结点元素，因此需要一个startIndex(我写的是idx)来防止结点重复

而本题最大的难点是，结点之间是存在重复元素的，而结点之间即便重复也可以继续使用，比如candidates = [10,1,2,7,6,1,5], target = 8 中，[1,1,6]就是一个合法的结果。但是最后的结果不允许有完全相同的结果集，即不允许存在两个[1,7] 。

先不考虑结果重复，写出大的框架：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    vector<int> candidates;
    int target;
    int sum = 0;
    void dfs(int idx) {
        if (sum > target) {
            return;
        } else if (sum == target) {
            result.push_back(path);
        }
        for (int i = idx; i < candidates.size(); i++) {
            int now = candidates[i];
            path.push_back(now);
            sum += now;
            dfs(i + 1);
            path.pop_back();
            sum -= now;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& a, int b) {

        candidates = a;
        target = b;
        used.resize(a.size());
        sort(candidates.begin(), candidates.end());
        dfs(0);
        return result;
    }
};

很经典的回溯模板，不记得就回去重新看代码随想录或者等之后补一次回溯基础的笔记

第一种去重思路

但是这个代码会导致结果重复，比如对于candidates = [10,1,2,7,6,1,5], target = 8 ，排序之后是candidates = [1,1,2,5,6,7,10], target = 8 。初始对第一个1 进行dfs后，将会得到所有包含1的结果。

这是因为对第一个1 进行dfs的过程中，后续所有其他的1 选或不选都会被遍历到。因此后续所有其他1 都不用再dfs了。

因此在每个元素进行dfs前只需要保证当前要dfs的元素是第一次被dfs，前面都没dfs过就可以了。

根据上述分析可知：

• 由于对第一个1 进行dfs时就已经得到了所有包含1 的结果，所以跳过后续的1并不会导致去重去多了

• 又因为对于单个元素的dfs过程中会受到idx 的制约，更不会去少了。单次dfs过程中是不会重复的

因此，我们要做的就是通过如下代码跳过不是第一次被dfs的元素：

if (i > idx && candidates[i-1] == candidates[i]) {
    continue;
}

如果前面有相同的元素，说明这个元素一定被dfs过；i > idx是为了防止单次dfs中某些结果被跳过了，idx是每一层遍历的起点，不管idx前是否有相同元素，它都一定需要被dfs。

完整代码如下：

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    vector<int> candidates;
    int target;
    int sum = 0;
    void dfs(int idx) {
        if (sum > target) {
            return;
        } else if (sum == target) {
            result.push_back(path);
        }
        for (int i = idx; i < candidates.size(); i++) {
            //此时说明已经对i-1遍历过了
            if (i > idx && candidates[i-1] == candidates[i]) {
                continue;
            }
            int now = candidates[i];
            path.push_back(now);
            sum += now;
            dfs(i + 1);
            path.pop_back();
            sum -= now;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& a, int b) {

        candidates = a;
        target = b;
        sort(candidates.begin(), candidates.end());
        dfs(0);
        return result;
    }
};

第二种去重思路(used数组)

其中还可以用used数组来实现一样的功能，used数组可以标识单次dfs中某个元素是否被使用过。在candidates[i-1] == candidates[i]的基础上，当used[i-1] == 1 时，说明i-1是在本次dfs中上一层被访问的。前面说过，单次dfs中是不会出现重复的，所以此时不跳过

但是used[i-1] == 0 时，只有一种情况：i-1这个元素在本次dfs中从未被访问，但它却出现在了当前元素的前面。前面的元素必然是在上层先被访问的，如果前面存在未被访问的元素，只能说明它曾经被dfs过了，是idx的存在让它没被本次dfs访问到，它还和当前元素相同，那当前元素就不能再dfs一次了。即：

if (i > 0 && candidates[i-1] == candidates[i] && used[i-1] == 0) {
    continue;
}

这个角度更难理解，但能加深对回溯去重和used数组的熟悉程度，后续有可能碰到需要用到它的题目。