Combination Sum II

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