leetcode40. 组合总和 II

分析

如果数组为[2,2,2]，target=4，可能产生[[2,2],[2,2],[2,2]]的情况，产生这种情况：

1. 第一次取第一个2时，第二次可以取第二个或第三个2，那么有两种选择。
2. 第一次取第二个2时，第二次可以取第三个2，只有一种选择，所以一共有三种取法。

为了去重，当第二次选择时，外面判断i>u&&nums[i]==nums[i-1]，如果条件成立则跳过此次循环。

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