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 class Solution { 2 public: 3 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { 4 int len = candidates.size(); 5 if (len == 0) 6 return {}; 7 vector<vector<int> > res; 8 vector<int> v; 9 sort(candidates.begin(), candidates.end()); 10 combinationSum2(candidates, target, res, v, len, 0); 11 return res; 12 } 13 private: 14 void combinationSum2(vector<int> &candidates, int target, vector<vector<int> > &res, vector<int> &v, int len, int begin) { 15 if (target == 0) { 16 res.push_back(v); 17 return ; 18 } 19 for (int i = begin; i < len && target >= candidates[i]; i++) { 20 if (i == begin || candidates[i] != candidates[i - 1]) { 21 v.push_back(candidates[i]); 22 combinationSum2(candidates, target - candidates[i], res, v, len, i + 1); 23 v.pop_back(); 24 } 25 } 26 } 27 };