## Saturday, January 26, 2013

### [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 (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]`
» 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:    }
``````