Combination Sum II

 1 public class Solution {
 2     public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         HashSet<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>();
 6         ArrayList<ArrayList<Integer>> finalresult = new ArrayList<ArrayList<Integer>>();
 7         ArrayList<Integer> output = new ArrayList<Integer>();
 8         int sum = 0;
 9         int len = num.length, depth = 0;
10         if(len == 0){
11             return finalresult;
12         }
13         Arrays.sort(num);
14         generate(result, output, sum, depth, len, target, num);
15         finalresult.addAll(result);
16         return finalresult;
17     }
18 
19     public void generate(HashSet<ArrayList<Integer>> result, ArrayList<Integer> output, int sum,
20             int depth, int len, int target, int[] candidates){
21             if(sum > target){
22                 return;
23             }
24             if(sum == target){
25                 ArrayList<Integer> tmp = new ArrayList<Integer>();
26                 tmp.addAll(output);
27                 result.add(tmp);
28                 return;
29             }
30             
31             for(int i = depth; i < len; i++){
32                 sum += candidates[i];
33                 output.add(candidates[i]);
34                 generate(result, output, sum, i+1, len, target, candidates);
35                 sum -= output.get(output.size() - 1);
36                 output.remove(output.size() - 1);
37             }
38         }
39 }