40. Combination Sum II

Bertha 。 2022-04-12 09:17 165阅读 0赞

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]
    ]

方法：回溯法

要点：（1）排序（2）去重（3）剪枝。

class Solution {
    public:
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            vector<vector<int>>  result;  //存储最终结果
            vector<int> item;            //回溯时，产生各个子集的数组
            set<vector<int>> setRes;      //去重使用的集合
            sort(candidates.begin(), candidates.end());  //排序
            generate(0, candidates, item, setRes, result, 0, target);
            return result;  
        }
     private:
        void generate(int i,vector<int>& candidates, vector<int>& item, set<vector<int>> &setRes, vector<vector<int>> &result, int sum,int target) 
        {
            if(i>= candidates.size() || sum > target)   //当元素已遍历完或者sum已经超过target
                return;
            
            sum += candidates[i];
            item.push_back(candidates[i]);                        //添加当前元素        
            if(sum == target && setRes.find(item) == setRes.end()) //在setRes中无法找到item
            {
                 setRes.insert(item);     
                 result.push_back(item); 
            }                   
            
            generate(i+1, candidates,item,setRes,result,sum,target);  //第一次递归调用
            sum -= candidates[i];
            item.pop_back();                                          //不添加当前元素
            generate(i+1, candidates,item,setRes,result,sum,target);  //第二次递归调用
        }     
    };