package com.fishercoder.solutions;

import com.fishercoder.common.utils.CommonUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * 40. Combination Sum II
 *
 * Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
 * Each number in C may only be used once in the combination.

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

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

    void backtracking(int[] candidates, int target, int start, List<Integer> curr, List<List<Integer>> result) {
        if (target > 0) {
            for (int i = start; i < candidates.length && target >= candidates[i]; i++) {
                if (i > start && candidates[i] == candidates[i - 1]) {
                    continue;//skip duplicates, this is one difference from Combination Sum I
                }
                curr.add(candidates[i]);
                backtracking(candidates, target - candidates[i], i + 1, curr, result);//i+1 is the other difference from Combination Sum I
                curr.remove(curr.size() - 1);
            }
        } else if (target == 0) {
            List<Integer> temp = new ArrayList(curr);
            result.add(temp);
        }
    }

    public static void main(String... args) {
        _40 test = new _40();
        int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        List<List<Integer>> result = test.combinationSum2(candidates, target);
        CommonUtils.printListList(result);
    }

}

@@ -33,58 +33,8 @@
 s;%0A%0A
-import com.fishercoder.common.utils.CommonUtils;%0A%0A
 impo
@@ -633,16 +633,56 @@
  _40 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -752,32 +752,36 @@
 rget) %7B%0A        
+  
+  
 List%3CList%3CIntege
@@ -818,16 +818,20 @@
         
+    
 Arrays.s
@@ -847,32 +847,36 @@
 dates);%0A        
+ 
+   
 backtracking(can
@@ -929,16 +929,20 @@
         
+   
+ 
 return r
@@ -948,27 +948,35 @@
 result;%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     void bac
@@ -1080,24 +1080,28 @@
 ) %7B%0A        
+    
 if (target %3E
@@ -1118,16 +1118,20 @@
         
+ 
+   
 for (int
@@ -1195,24 +1195,28 @@
 %5Bi%5D; i++) %7B%0A
+    
             
@@ -1294,16 +1294,20 @@
         
+    
 continue
@@ -1380,34 +1380,42 @@
                 
+   
+ 
 %7D%0A
+    
                 
@@ -1439,16 +1439,20 @@
 es%5Bi%5D);%0A
+    
         
@@ -1594,24 +1594,28 @@
             
+    
 curr.remove(
@@ -1636,32 +1636,36 @@
 1);%0A            
+    
 %7D%0A        %7D else
@@ -1658,16 +1658,20 @@
         
+ 
+   
 %7D else i
@@ -1704,378 +1704,68 @@
     
-List%3CInteger%3E temp = new ArrayList(curr);%0A            result.add(temp);%0A        %7D%0A    %7D%0A%0A    public static void main(String... args) %7B%0A        _40 test = new _40();%0A        int%5B%5D candidates = new int%5B%5D%7B10, 1, 2, 7, 6, 1, 5%7D;%0A        int target = 8;%0A        List%3CList%3CInteger%3E%3E result = test.combinationSum2(candidates, target);%0A        CommonUtils.printListList(result);
+    result.add(new ArrayList(curr));%0A            %7D%0A        %7D
 %0A   
@@ -1769,9 +1769,8 @@
     %7D%0A%0A%7D
-%0A

refactor 40