[LeetCode] Combination Sum II, Solution

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 (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ â‰¤ a₂ â‰¤ … ≤ a_k).
• 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] 

» Solve this problem

[Thoughts]
Very similar with previous "Combination Sum". The only difference is marked as red in Code part. Need to handle the index and skip duplicate candidate.


[Code]

1:    vector<vector<int> > combinationSum2(vector<int> &num, int target) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      // Start typing your C/C++ solution below  
5:      // DO NOT write int main() function  
6:      vector<vector<int> > result;  
7:      vector<int> solution;  
8:      int sum=0;  
9:      std::sort(num.begin(), num.end());  
10:      GetCombinations(num,sum, 0, target, solution, result);  
11:      return result;  
12:    }  
13:    void GetCombinations(  
14:      vector<int>& candidates,  
15:      int& sum,  
16:      int level,  
17:      int target,  
18:      vector<int>& solution,  
19:      vector<vector<int> >& result)  
20:    {  
21:      if(sum > target) return;  
22:      if(sum == target)  
23:      {  
24:        result.push_back(solution);  
25:        return;  
26:      }  
27:      for(int i =level; i< candidates.size(); i++)  
28:      {  
29:        sum+=candidates[i];  
30:        solution.push_back(candidates[i]);  
31:        GetCombinations(candidates, sum, i+1, target, solution, result);  
32:        solution.pop_back();  
33:        sum-=candidates[i];    
34:        while(i<candidates.size()-1 && candidates[i] == candidates[i+1]) i++;  
35:      }  
36:    }