https://leetcode.com/problems/combination-sum-ii/description/

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

和前面的题比较就是不能出现重复的元素

绕后copy过来代码自己改呗

开始用的lowB的排序后vector unique去重

class Solution {
public:
    vector<vector<int>> tot;
    void dfs(int x,vector<int>& c,int target,vector<int> ans,int s){
        for(int i=s+1;i<c.size();i++){
            ans.push_back(c[i]);
            if(x+c[i]<target)
                dfs(x+c[i],c,target,ans,i);
            else if(x+c[i]==target){
                tot.push_back(ans);                    
            }
            ans.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> ans;
        ans.empty();
        tot.empty();
        sort(candidates.begin(),candidates.end());
        dfs(0,candidates,target,ans,-1);
        sort(tot.begin(),tot.end());
        tot.erase(unique(tot.begin(), tot.end()), tot.end());
        return tot;

    }
};

后来看讨论区中说可以限制

循环的时候 举个例子

1,2,2,3,4,6 target是8

那么如果循环中到了1->2->2这种 前后虽然相等 但是前后相邻 也就是c[i]==c[i-1]&&i==s+1 这种情况是正常要计算的

如果到了1->2的时候 下一次 遇到1->2的时候 由于c[i]==c[i-1]&&i>s+1 所以continue

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

    }
};

12ms->8ms