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]

1 class Solution { 2 public: 3     vector
     
      
        > combinationSum2(vector
       
         &num, int target) { 4         sort(num.begin(), num.end()); 5         vector
        
         
           > res; 6         vector
          
            com; 7 combinationSum2(num, target, res, com, 0); 8 return res; 9 }10 11 void combinationSum2(vector
           
            & num, int target, vector
            
             
               > &res, vector
              
                &com, int start)12 {13 if(target == 0) {14 res.push_back(com);15 return;16 }17 for(int i = start; i < num.size() && num[i] <= target; i++) {18 if(i > start && num[i] == num[i-1]) continue; // !duplicate cases19 com.push_back(num[i]);20 combinationSum2(num, target-num[i], res, com, i+1);21 com.pop_back();22 }23 }24 };