package advanced.combinatorial.subset.lc040_combinationsum2;

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

/**
 * 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 Solution {

    // My 2nd: O(2^N) time, O(N) space
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        doCombineSum(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void doCombineSum(List<List<Integer>> result,
                              List<Integer> path, int[] candidates, int target, int k) {
        if (target <= 0) {
            if (target == 0) {
                result.add(new ArrayList<>(path));
            }
            return;
        }

        for (int i = k; i < candidates.length; i++) {
            if (i > k && candidates[i] == candidates[i - 1]) { // Very nice!!! Or use prev, both way is better than mine
                continue;
            }
            path.add(candidates[i]);
            doCombineSum(result, path, candidates, target - candidates[i], i + 1);
            path.remove(path.size() - 1);

            /*while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) { // bypass duplidate candidates
                i++;
            }*/
            /* candidates[i] <> candidates[i + 1], then i++ in for move i to what we want */
        }
    }

    // My 1st
    public List<List<Integer>> combinationSum2_old(int[] candidates, int target) {
        // Avoid duplicates: List equals cannot handle like [2,1,5] and [1,2,5]
        Set<List<Integer>> result = new HashSet<>();
        Arrays.sort(candidates);

        boolean[] presents = new boolean[candidates.length];
        subset(result, presents, candidates, target, 0);
        return new ArrayList<>(result);
    }

    private void subset(Set<List<Integer>> result, boolean[] presents,
                        int[] candidates, int target, int k) {
        if (target == 0) {
            List<Integer> r = new ArrayList<>();
            for (int i = 0; i < k; i++) { // must be <k (not candidates.length) to avoid gabage data
                if (presents[i]) {
                    r.add(candidates[i]);
                }
            }

            if (!result.contains(r)) {
                result.add(r);
            }
            return;
        }

        if (k == candidates.length || target < 0) { // could cause time limit exceeded if put outside previous if
            return;
        }

        presents[k] = false;
        subset(result, presents, candidates, target, k+1);

        presents[k] = true;
        subset(result, presents, candidates, target-candidates[k], k+1);
    }

}

@@ -718,16 +718,1050 @@
 tion %7B%0A%0A
+    // Variants:%0A    // 39-Combination Sum: candidates can be used many times =%3E dfs(..., i)%0A    // 40-Combination Sum II: many times + duplicate =%3E if(...) continue%0A    // LintCode II: only once =%3E dfs(..., i+1)%0A    public List%3CList%3CInteger%3E%3E combinationSum2_3(int%5B%5D nums, int target) %7B%0A        Arrays.sort(nums);%0A        List%3CList%3CInteger%3E%3E ret = new ArrayList%3C%3E();%0A        if (nums.length %3E 0) dfs(ret, new ArrayList%3C%3E(), nums, target, 0);%0A        return ret;%0A    %7D%0A%0A    private void dfs(List%3CList%3CInteger%3E%3E ret, List%3CInteger%3E path, int%5B%5D nums, int target, int start) %7B%0A        if (target %3C= 0) %7B%0A            if (target == 0) ret.add(new ArrayList%3C%3E(path));%0A            return;%0A        %7D%0A        for (int i = start; i %3C nums.length; i++) %7B%0A            if (i %3E start && nums%5Bi%5D == nums%5Bi - 1%5D) continue; // Comb-2: de-duplicate%0A            path.add(nums%5Bi%5D);%0A            dfs(ret, path, nums, target - nums%5Bi%5D, i); // Comb-1: each candidate used any time, i+1 for only once%0A            path.remove(path.size() - 1);%0A        %7D%0A    %7D%0A%0A
     // M

combination sum 2