Combination Sum

 1 public class Solution {
 2     public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
 3         // Start typing your Java solution below
 4         // DO NOT write main() function
 5         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 6         int len = candidates.length, depth = 0;
 7         if(len == 0){
 8             return result;
 9         }
10         ArrayList<Integer> output = new ArrayList<Integer>();
11         int sum = 0;
12         Arrays.sort(candidates);
13         generate(result, output, sum, depth, len, target, candidates);
14         return result;
15     }
16     
17     public void generate(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> output, int sum,
18             int depth, int len, int target, int[] candidates){
19             if(sum > target){
20                 return;
21             }
22             if(sum == target){
23                 ArrayList<Integer> tmp = new ArrayList<Integer>();
24                 tmp.addAll(output);
25                 result.add(tmp);
26                 return;
27             }
28             
29             for(int i = depth; i < len; i++){
30                 sum += candidates[i];
31                 output.add(candidates[i]);
32                 generate(result, output, sum, i, len, target, candidates);
33                 sum -= output.get(output.size() - 1);
34                 output.remove(output.size() - 1);
35             }
36         }
37 }