## Monday, November 17, 2014

### [LeetCode] Combination Sum I, II

Combination Sum I

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
• All numbers (including target) will be positive integers.
• Elements in a combination (a1a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.
For example, given candidate set `2,3,6,7` and target `7`,
A solution set is:
`[7]`
`[2, 2, 3]`

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.
Note:
• All numbers (including target) will be positive integers.
• Elements in a combination (a1a2, … , 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]`

1. 不回头扫，在扫描candidates[i]时，对candidate[i: n-1]递归查找target-candidates[i]。
2. 每层扫描的时候跳过重复的candidates。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27``` ```class Solution { public: vector > combinationSum(vector &candidates, int target) { vector > allSol; vector sol; if(candidates.empty()) return allSol; sort(candidates.begin(),candidates.end()); findCombSum(candidates, 0, target, sol, allSol); return allSol; } void findCombSum(vector &candidates, int start, int target, vector &sol, vector> &allSol) { if(target==0) { allSol.push_back(sol); return; } for(int i=start; istart && candidates[i]==candidates[i-1]) continue; if(candidates[i]<=target) { sol.push_back(candidates[i]); findCombSum(candidates, i, target-candidates[i], sol, allSol); sol.pop_back(); } } } }; ```

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27``` ```class Solution { public: vector > combinationSum2(vector &num, int target) { vector > allSol; if(num.empty()) return allSol; sort(num.begin(),num.end()); vector sol; findCombSum2(num, 0, target, sol, allSol); return allSol; } void findCombSum2(vector &num, int start, int target, vector &sol, vector > &allSol) { if(target==0) { allSol.push_back(sol); return; } for(int i=start; istart && num[i]==num[i-1]) continue; if(num[i]<=target) { sol.push_back(num[i]); findCombSum2(num, i+1, target-num[i], sol, allSol); sol.pop_back(); } } } }; ```

#### 1 comment:

1. 要剪枝叶啊，
if(num[i]<=target) ...
else break;