Combination Sum

 1 public class Solution {
 2         public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
 3             ArrayList<Integer> output= new ArrayList<Integer>();
 4             ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
 5             if(candidates.length<=0) return res;
 6             Arrays.sort(candidates);//don‘t forget sort
 7             DFS(res,output,0,candidates,0,target);
 8             return res;
 9         }
10         public void DFS(ArrayList<ArrayList<Integer>>res,ArrayList<Integer> output,int start,int[]can,int sum,int target){
11             if(sum>target) return;
12             if(sum==target){
13                 ArrayList<Integer> temp = new ArrayList<Integer>();
14                 temp.addAll(output);
15                 res.add(temp);
16                 return;
17             }
18             for(int i=start;i<can.length;i++){
19                 sum +=can[i];
20                 output.add(can[i]);
21                 DFS(res,output,i,can,sum,target);
22                 sum-=output.get(output.size()-1);
23                 output.remove(output.size()-1);
24             }
25         }
26     }