package com.fishercoder.solutions;

import com.fishercoder.common.utils.CommonUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/***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);
        helper(candidates, target, 0, new ArrayList(), result);
        return result;
    }

    void helper(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]);
                helper(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);
    }


}

@@ -158,17 +158,49 @@
 ist;%0A/**
-*
+%0A * 40. Combination Sum II%0A *%0A * 
 Given a 
@@ -333,17 +333,18 @@
 s to T.%0A
-%0A
+ *
  Each nu
@@ -658,16 +658,18 @@
 1, 6%5D%0A %5D
+%0A 
 */%0Apubli
@@ -849,38 +849,44 @@
 dates);%0A        
-helper
+backtracking
 (candidates, tar
@@ -958,22 +958,28 @@
    void 
-helper
+backtracking
 (int%5B%5D c
@@ -1421,14 +1421,20 @@
     
-helper
+backtracking
 (can
@@ -2024,11 +2024,10 @@
 %0A    %7D%0A%0A
-%0A
 %7D%0A

refactor 40