40. Combination Sum II-蒲公英云

40. Combination Sum II

Bertha 。 2022-04-12 09:17 294阅读 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);  //第二次递归调用
    }     
};