39. Combination Sum Leetcode Java

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] 

Solution:

Classic recursion problem.

Classic recursion solution:

1. base, terminating case:

if(target==0) ...

2. recursion steps: 

   a) try current candidate: items.add(candidate[i]);

   b) recursion to next level: helper(target-candidate[i]...);

    c) backtrack to current level, remove current candidate: items.remove(item.size()-1---> "candidate[i]")
Tips: 
1. Skip duplicated elements to avoid non necessary recursion and duplicated result.
2. Since element can be used multi times, the next level will be start with the same index as the current level. 

  public List<List<Integer>> combinationSum(int[] candidates, int target) {  
     List<List<Integer>> res=new ArrayList<List<Integer>>();  
     if(candidates==null || candidates.length==0) return res;  
     Arrays.sort(candidates);  
     List<Integer> item=new ArrayList<Integer>();  
     helper(candidates,0,target,item,res);  
     return res;  
   }  
   public void helper(int[] candidates, int index, int target, List<Integer> item, List<List<Integer>> res){  
     if(target==0){  
       List<Integer> temp= new ArrayList<Integer>(item);  
       res.add(temp);  
       return;  
     }  
     for(int i=index;i<candidates.length;i++){  
       if(i>0 && candidates[i]==candidates[i-1]) continue;  
        if(target-candidates[i]<0) return;  
       item.add(candidates[i]);  
       helper(candidates,i,target-candidates[i],item,res);  
       item.remove(item.size()-1);  
     }  
   }