Combination Sum

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 (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 2,3,6,7 and target 7, A solution set

is: [7] [2, 2, 3]

思路： 把target number 传入， 每次加入一个数字，就把target number 减去这个数字递归。 当target number == 0 时，说明此时list中的数字的和为target number。 就可以将这组数字加入list里面。 注意可以重复加数字， 所以每次递归传的index就是i。

public class Solution {    public List
    
     
      > combinationSum(int[] candidates, int target) {        List
      
       
        > result = new ArrayList
        
         
          >(); List
          
            list = new ArrayList
           
            (); Arrays.sort(candidates); int sum = target; helper(result,list, sum,candidates,0); return result; } private void helper(List
            
             
              > result, List
              
                list,int sum, int[] candidates,int index) { if (sum == 0) { result.add(new ArrayList
               
                (list)); return; } for (int i = index; i < candidates.length; i++) { if (sum < 0) { break; } list.add(candidates[i]); helper(result,list, sum - candidates[i], candidates,i); list.remove(list.size() - 1); } }}