40. 组合总和 II

思路

为什么会出现重复？
以{1，1，7}和target = 8为例，
如果不选0号位置的1，那么1号位置的1就也不应该选
否则0号位置的1和7构成一个结果
在不选0号位置时，1号位置的1和7又构成一个结果
从而发生重复
所以去重的思路就是如果不选某个元素，那么之后和他相等的元素都应该跳过

代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> res;
        dfs(candidates, res, 0, target);
        return ans;
    }

    void dfs(vector<int> &candidates, vector<int>& res, int depth, int target)
    {
        if(target == 0)
        {
            ans.push_back(res);
            return;   
        }
        if(depth == candidates.size() || target < candidates[depth]) return;

        int val = candidates[depth];

        // not choose
        for(int j = depth + 1; j < candidates.size(); j++)
            if(candidates[j] != candidates[depth])
            {
                dfs(candidates, res, j, target);
                break;
            }

        // choose 
        res.push_back(val);
        dfs(candidates, res, depth + 1, target - val);
        res.pop_back();
    }
};