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]

 

1 public class Solution { 2     ArrayList
     
      
       > result = null; 3     public ArrayList
       
        
         > combinationSum(int[] candidates, int target) { 4         // Note: The Solution object is instantiated only once and is reused by each test case. 5         result = new ArrayList
         
          
           >(); 6 getSolution(new ArrayList
           
            (), target, candidates); 7 return result; 8 } 9 public void getSolution(ArrayList
            
              row, int target, int[] candidates){10 int i = 0;11 if(target == 0){12 result.add(row);13 }14 while(i < candidates.length && candidates[i] <= target){15 row.add(candidates[i]);16 target -= candidates[i];17 getSolution(new ArrayList
             
              (row),target,candidates);18 row.remove(row.size() - 1);19 target += candidates[i];20 i ++;21 }22 if(i == 0){23 return;24 }25 }26 }
             
            
           
          
         
        
       
      
     

没有去重。

eg: [1,1,2] 3

去重包括两部分，1.array 里面有重复： 1，1

                     2.顺序， 如 1,2 ; 2, 1

对于1，先将数组去重。

对于2，后面的选择范围只能从当前选择的元素开始，只能选不比它小的元素。

1 public class Solution { 2     ArrayList
     
      
       > result = null; 3     public ArrayList
       
        
         > combinationSum(int[] candidates, int target) { 4         // Note: The Solution object is instantiated only once and is reused by each test case. 5         Arrays.sort(candidates); 6         int start = 0; 7         for(int i = 1; i < candidates.length; i ++){ 8             if(candidates[i] != candidates[start]){ 9                 candidates[++start] = candidates[i];10             }11         }12         result = new ArrayList
         
          
           >();13 getSolution(new ArrayList
           
            (), target, candidates, start, 0);14 return result;15 }16 public void getSolution(ArrayList
            
              row, int target, int[] candidates, int len, int pos){17 int i = pos;18 if(target == 0){19 result.add(row);20 }21 while(i <= len && candidates[i] <= target){22 row.add(candidates[i]);23 target -= candidates[i];24 getSolution(new ArrayList
             
              (row), target, candidates, len, i);25 row.remove(row.size() - 1);26 target += candidates[i];27 i ++;28 } 29 }30 }
             
            
           
          
         
        
       
      
     

 第三遍：

1 public class Solution { 2     public List
     
      
       > combinationSum(int[] candidates, int target) { 3         int len = 0; 4         Arrays.sort(candidates); 5         for(int i = 0; i < candidates.length; i ++){ 6             if(i == 0 || candidates[i] != candidates[i - 1]){ 7                 candidates[len ++] = candidates[i]; 8             } 9         }10         List
       
        
         > result = new ArrayList
         
          
           >();11 findElement(candidates, 0, len, result, new ArrayList
           
            (), target);12 return result;13 }14 15 public void findElement(int[] arr, int start, int end, List
            
             
              > result, ArrayList
              
                row, int tar){16 if(tar == 0) result.add(row);17 for(int i = start; i < end; i ++){18 if(arr[i] <= tar){19 ArrayList
               
                 rown = new ArrayList
                
                  (row);20 rown.add(arr[i]);21 findElement(arr, i, end, result, rown, tar - arr[i]);22 }23 }24 }25 }