package com.fishercoder.solutions;

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 static class Solution1 {
      public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList();
        Arrays.sort(candidates);
        backtracking(candidates, 0, result, target, new ArrayList());
        return result;
      }

      void backtracking(int[] candidates, int start, List<List<Integer>> result, int target,
          List<Integer> curr) {
        if (target > 0) {
          for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target || (i > start && candidates[i - 1] == candidates[i])) {
              continue;
            }
            curr.add(candidates[i]);
            backtracking(candidates, i + 1, result, target - candidates[i], curr);
            curr.remove(curr.size() - 1);
          }
        } else if (target == 0) {
          result.add(new ArrayList(curr));
        }
      }
    }
}

@@ -109,515 +109,8 @@
 st;%0A
-/**%0A * 40. Combination Sum II%0A *%0A * 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.%0A * Each number in C may only be used once in the combination.%0A%0A Note:%0A All numbers (including target) will be positive integers.%0A The solution set must not contain duplicate combinations.%0A For example, given candidate set %5B10, 1, 2, 7, 6, 1, 5%5D and target 8,%0A A solution set is:%0A %5B%0A %5B1, 7%5D,%0A %5B1, 2, 5%5D,%0A %5B2, 6%5D,%0A %5B1, 1, 6%5D%0A %5D%0A */
 %0Apub
@@ -162,16 +162,18 @@
 tion1 %7B%0A
+  
       pu
@@ -249,24 +249,28 @@
 ) %7B%0A        
+ 
+   
 List%3CList%3CIn
@@ -311,16 +311,20 @@
         
+    
 Arrays.s
@@ -340,32 +340,36 @@
 dates);%0A        
+   
+ 
 backtracking(can
@@ -410,24 +410,28 @@
 rayList());%0A
+    
         retu
@@ -451,11 +451,15 @@
     
+  
 %7D%0A%0A
+  
     
@@ -547,16 +547,32 @@
 target,%0A
+                
         
@@ -591,24 +591,28 @@
 er%3E curr) %7B%0A
+    
         if (
@@ -635,16 +635,22 @@
         
+      
 for (int
@@ -687,24 +687,32 @@
 gth; i++) %7B%0A
+        
             
@@ -808,16 +808,26 @@
         
+      
+    
 continue
@@ -832,34 +832,49 @@
 ue;%0A            
-%7D%0A
+        %7D%0A       
             curr
@@ -865,24 +865,25 @@
             
+ 
 curr.add(can
@@ -895,16 +895,24 @@
 es%5Bi%5D);%0A
+        
         
@@ -994,24 +994,32 @@
             
+        
 curr.remove(
@@ -1038,34 +1038,44 @@
 - 1);%0A          
+   
-%7D%0A
+   %7D%0A    
         %7D else i
@@ -1102,16 +1102,22 @@
         
+   
+   
 result.a
@@ -1145,26 +1145,32 @@
 ));%0A        
-%7D%0A
+    %7D%0A  
       %7D%0A    

refactor 40