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]
]
class Solution { public: vector<pair<int,int>> freg; vector<vector<int>> ans; vector<int> sequence; void dfs(int pos,int rest){ if(rest == 0){ ans.emplace_back(sequence); return; } if(pos == freg.size() || rest<freg[pos].first){ return;//加上最后一个数后，超过了对应的target } dfs(pos+1,rest); int most = min(rest/freg[pos].first,freg[pos].second); for(int i=1;i<=most;++i){ sequence.emplace_back(freg[pos].first); dfs(pos+1,rest-i*freg[pos].first); } for(int i=1;i<=most;++i){ sequence.pop_back();//恢复现场，为了便于后面的进一步递归 } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); for(int num:candidates){ if(freg.empty() || num!=freg.back().first){ freg.emplace_back(num,1); } else{ ++freg.back().second; } } dfs(0,target); return ans; } };
注意：1.回溯的方式，对于列表中的每个数都有两种选择，选择或者不被选择，类似一个二叉树的方式进行递归。2.为了避免重复枚举，将所有一样的数字放在一起，按照该数字可能出现的次数，逐个进行枚举判断。
原文：https://www.cnblogs.com/zmachine/p/13644221.html