Combination Sum II
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.
http://www.lintcode.com/en/problem/combination-sum-ii/
Discussion
Combination Sum 问题的扩展,跟Subsets II问题一样的方法去充就可以了。if(i!=start && nums[i] == nums[i-1]) continue;
-- 这种情况下就跳过当前number。
Solution
class Solution {
public:
/**
* @param num: Given the candidate numbers
* @param target: Given the target number
* @return: All the combinations that sum to target
*/
vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
// write your code here
vector<vector<int> > result;
int n = candidates.size();
if(n==0) return result;
vector<int> solution;
sort(candidates.begin(), candidates.end());//忘记一百次!!!
dfs(candidates, target, solution, 0, result);
return result;
}
void dfs(vector<int> &candidates, int gap, vector<int> &solution, int start,
vector<vector<int> > &result) {
if(gap == 0) {
result.push_back(solution);
return;
}
int n = candidates.size();
for(int i=start; i<n; i++) {
if(gap < candidates[i]) {
break;
}
if(i != start && candidates[i] == candidates[i-1])
continue;
solution.push_back(candidates[i]);
dfs(candidates, gap-candidates[i], solution, i+1, result);
solution.pop_back();
}
}
};
`