原题地址（中等）

方法1—回溯

这题和第39题组合总和极其相似，实际上会了那道题，这道题就自然而然了。
附上39题题解。
39. 组合总和
这题有稍稍的变动，就是元素不能重复使用了， 但是数组中可以含有重复的元素 。

可以在39题最基本的回溯解法上加上哈希表来去重，此解法不再赘述。
第二个就是继续沿用威威哥的解法。
贴出39题代码中的回溯函数。

void dfs(vector<int> candidates, int k, int cur, int end){
    if(k < 0)  return;
    if(k == 0){
        vv.push_back(v);
        return ;
    }
    // 回溯
    for(int i=cur; i<=end; i++){
        v.push_back(candidates[i]);
        dfs(candidates, k-candidates[i], i, end);
        v.pop_back();
    }
}

因为39题是可以重复利用当前元素，所以循环中会出现 dfs(candidates, k-candidates[i], i, end); ，如果不能重复利用元素，那么代码应该改为 dfs(candidates, k-candidates[i], ``i+1``, end);

但是这样仍然不能避免重复，因为有可能会出现 candidates=[1,1,1,1,1,2] 这种同一元素多次出现的情况。这样我们怎么处理呢？
答案就是只处理第一个 1 ，剩下的 1 直接忽略掉，也就是

if(i > cur && candidates[i] == candidates[i-1])
    continue;

最终代码

class Solution {
public:
    set<vector<int>> ans;
    vector<int> v;
    void dfs(vector<int> candidates, int cur, int end, int target){
        if(target==0){
            ans.insert(v);
            return;
        }
        if(cur > end || candidates[cur] > target)  return;
        for(int i=cur; i<=end; i++ ){
            if(i > cur && candidates[i] == candidates[i-1])
                continue;
            v.push_back(candidates[i]);
            dfs(candidates, i+1, end, target-candidates[i]);
            v.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        int n = candidates.size();
        if(n==0)    return {};
        dfs(candidates, 0, n-1, target);
        vector<vector<int>> vv(ans.begin(), ans.end());
        return vv;
    }
};