package com.fishercoder.solutions;

import com.fishercoder.common.utils.CommonUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 39. Combination Sum
 *
 * Given a set of candidate numbers (C) (without duplicates) and a target number (T),
 * find all unique combinations in C where the candidate numbers sums to T.

 The same repeated number may be chosen from C unlimited number of times.

 Note:
 All numbers (including target) will be positive integers.
 The solution set must not contain duplicate combinations.
 For example, given candidate set [2, 3, 6, 7] and target 7,
 A solution set is:
 [
 [7],
 [2, 2, 3]
 ]*/
public class _39 {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList();
        Arrays.sort(candidates);
        backtracking(candidates, target, 0, new ArrayList(), result);
        return result;
    }

    private void backtracking(int[] candidates, int target, int startIndex, List<Integer> curr, List<List<Integer>> result) {
        if (target > 0) {
            int prev = -1;
            for (int i = startIndex; i < candidates.length; i++) {
                if (candidates[i] > target) {
                    return;//this is one very important step to optimize this algorithm: pruning
                }
                if (prev != -1 && prev == candidates[i]) {
                    continue;
                }
                curr.add(candidates[i]);
                backtracking(candidates, target - candidates[i], i, curr, result);
                curr.remove(curr.size() - 1);
            }
        } else if (target == 0) {
            result.add(new ArrayList(curr));
        }
    }


    public static void main(String... args) {
        _39 test = new _39();
        int[] candidates = new int[]{2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> result = test.combinationSum(candidates, target);
        CommonUtils.printListList(result);
    }

}

@@ -33,58 +33,8 @@
 s;%0A%0A
-import com.fishercoder.common.utils.CommonUtils;%0A%0A
 impo
@@ -625,16 +625,56 @@
  _39 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -743,32 +743,36 @@
 rget) %7B%0A        
+    
 List%3CList%3CIntege
@@ -809,16 +809,20 @@
         
+ 
+   
 Arrays.s
@@ -838,16 +838,20 @@
 dates);%0A
+    
         
@@ -916,24 +916,28 @@
 t);%0A        
+  
+  
 return resul
@@ -939,16 +939,20 @@
 result;%0A
+    
     %7D%0A%0A 
@@ -958,15 +958,11 @@
     
-private
+   
  voi
@@ -1015,21 +1015,16 @@
 nt start
-Index
 , List%3CI
@@ -1071,24 +1071,28 @@
 ) %7B%0A        
+    
 if (target %3E
@@ -1105,31 +1105,8 @@
     
-        int prev = -1;%0A
     
@@ -1135,13 +1135,8 @@
 tart
-Index
 ; i 
@@ -1159,24 +1159,28 @@
 gth; i++) %7B%0A
+    
             
@@ -1229,24 +1229,28 @@
             
+    
 return;//thi
@@ -1250,68 +1250,8 @@
 n;//
-this is one very important step to optimize this algorithm: 
 prun
@@ -1274,117 +1274,18 @@
     
-%7D%0A
     
+%7D%0A
     
-        if (prev != -1 && prev == candidates%5Bi%5D) %7B%0A                    continue;%0A                %7D%0A
     
@@ -1321,16 +1321,20 @@
 es%5Bi%5D);%0A
+    
         
@@ -1420,24 +1420,28 @@
             
+ 
+   
 curr.remove(
@@ -1470,26 +1470,32 @@
         
-%7D%0A
+    %7D%0A  
         
 %7D else i
@@ -1486,16 +1486,18 @@
         
+  
 %7D else i
@@ -1510,24 +1510,28 @@
 get == 0) %7B%0A
+    
             
@@ -1575,294 +1575,28 @@
     
-%7D%0A
     %7D%0A
-%0A%0A
     
-public static void main(String... args) %7B%0A        _39 test = new _39();%0A        int%5B%5D candidates = new int%5B%5D%7B2, 3, 6, 7%7D;%0A        int target = 7;%0A        List%3CList%3CInteger%3E%3E result = test.combinationSum(candidates, target);%0A        CommonUtils.printListList(result);
+    %7D
 %0A    %7D%0A
-%0A
 %7D%0A

refactor 39