Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers
sums to T.
Each number in C may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- Elements in a combination (a1, a2,
… , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤
… ≤ ak). - The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5
and target 8
,
A solution set is: [1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
关键是判断重复,如果两个数相同,只有第一个数使用了,才能使用第二个数。
class Solution { public: vector<vector<int> > combinationSum2(vector<int> &num, int target) { sort(num.begin(), num.end()); vector<int> v; combinationSumUtil(num, v, target, 0); return result; } void combinationSumUtil(vector<int> &candidates, vector<int> &comb, int sum, int start) { if (sum == 0) { result.push_back(comb); return; } for (int i = start; i < candidates.size(); ++i) { if (candidates[i] <= sum) { if (!isDuplicate(candidates, comb, i)) { comb.push_back(candidates[i]); combinationSumUtil(candidates, comb, sum - candidates[i], i + 1); comb.pop_back(); } } else { break; } } } bool isDuplicate(vector<int> &candidates, vector<int> &comb, int index) { int same = 0; int i = index; while (--i >= 0) { if (candidates[i] == candidates[i+1]) { ++same; } else { break; } } i = comb.size(); while (--i >= 0) { if (comb[i] == candidates[index]) { --same; } else { break; } } return (same > 0); } private: vector<vector<int> > result; };
也可以通过每次出栈的时候跳过相同元素来避免重复。
class Solution { public: vector<vector<int> > combinationSum2(vector<int> &num, int target) { sort(num.begin(), num.end()); vector<int> v; combinationSumUtil(num, v, target, 0); return result; } void combinationSumUtil(vector<int> &candidates, vector<int> &comb, int sum, int start) { if (sum == 0) { result.push_back(comb); return; } for (int i = start; i < candidates.size(); ++i) { if (candidates[i] <= sum) { comb.push_back(candidates[i]); combinationSumUtil(candidates, comb, sum - candidates[i], i + 1); comb.pop_back(); while (i + 1 < candidates.size() && candidates[i] == candidates[i+1]) { ++i; } } else { break; } } } private: vector<vector<int> > result; };