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 (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 

2,3,6,7 and target 

7, 

A solution set is: 

[7] 

[2, 2, 3] 

[Thoughts]

This is a normal recursion question. For each candidate, add and verify the target. If it hit, add it as a part of solution.

[Code]

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