package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode.com/problems/combination-sum/
 */
public class Problem39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Set<List<Integer>> set = new HashSet<>();
        combinationSum(candidates, target, new ArrayList<>(), set);
        for (List<Integer> list : set) {
            result.add(list);
        }
        return result;
    }

    private void combinationSum(int[] candidates, int target, List<Integer> accu,
                                Set<List<Integer>> result) {
        if (target == 0) {
            Collections.sort(accu);
            result.add(accu);
            return;
        }
        if (target < 0) {
            return;
        }
        for (int i = 0; i < candidates.length; i++) {
            List<Integer> newAccu = new ArrayList<>(accu);
            newAccu.add(candidates[i]);
            combinationSum(candidates, target - candidates[i], newAccu, result);
        }
    }
}

@@ -61,89 +61,11 @@
 til.
-Collections;%0Aimport java.util.HashSet;%0Aimport java.util.List;%0Aimport java.util.Se
+Lis
 t;%0A%0A
@@ -253,22 +253,22 @@
 teger%3E%3E 
-result
+answer
  = new A
@@ -285,58 +285,8 @@
 ();%0A
-        Set%3CList%3CInteger%3E%3E set = new HashSet%3C%3E();%0A
     
@@ -323,16 +323,19 @@
  target,
+ 0,
  new Arr
@@ -350,95 +350,17 @@
 (), 
-set);%0A        for (List%3CInteger%3E list : set) %7B%0A            result.add(list
+answer
 );%0A
-        %7D%0A
     
@@ -370,22 +370,22 @@
  return 
-result
+answer
 ;%0A    %7D%0A
@@ -446,16 +446,27 @@
  target,
+ int index,
  List%3CIn
@@ -514,10 +514,11 @@
     
-Se
+Lis
 t%3CLi
@@ -530,22 +530,22 @@
 teger%3E%3E 
-result
+answer
 ) %7B%0A    
@@ -583,60 +583,41 @@
     
-Collections.sort(accu);%0A            result.add
+answer.add(new ArrayList%3C%3E
 (accu)
+)
 ;%0A  
@@ -721,17 +721,21 @@
 int i = 
-0
+index
 ; i %3C ca
@@ -774,71 +774,9 @@
     
-List%3CInteger%3E newAccu = new ArrayList%3C%3E(accu);%0A            newA
+a
 ccu.
@@ -862,23 +862,65 @@
 i%5D, 
-newA
+i, a
 ccu, 
-result
+answer);%0A            accu.remove(accu.size() - 1
 );%0A 

Solve problem 39