[Leetcode] Combination Sum

 1 import java.util.*;
 2 
 3 public class Solution {
 4     public void dp(int[] candidates, int index, int target,List<List<Integer>> lists,
 5     List<Integer> tmplist, int tmpsum){
 6         if(tmpsum==target) {
 7             List<Integer> l = new LinkedList<Integer>();
 8             l.addAll(tmplist);
 9             lists.add(l);
10             return;
11         }
12         if(tmpsum>target||index==candidates.length) return;
13         int maxnum=(target-tmpsum)/candidates[index];
14         for(int i=0;i<maxnum;i++){
15             tmplist.add(candidates[index]);
16             dp(candidates,index+1,target,lists,tmplist,tmpsum+candidates[index]*(i+1));
17         }
18         for(int i=0;i<maxnum;i++){
19             tmplist.remove(tmplist.size()-1);
20         }
21         dp(candidates,index+1,target,lists,tmplist,tmpsum);
22     }
23     public List<List<Integer>> combinationSum(int[] candidates, int target) {
24         // if the candidates are not sorted ,then we need to sort each conditioned 
25         // tmplist. Because it need the tmplist should be sorted.
26         Arrays.sort(candidates);
27         List<List<Integer>> lists =new LinkedList<List<Integer>> ();
28         List<Integer> tmplist = new LinkedList<Integer>();
29         dp(candidates,0,target,lists,tmplist,0);
30         return lists;
31     }
32 }