40. Combination Sum II (not use before so int I = start, dfs(i+1), and sort

time: O(2^n), candidate choose or not choose, n times

space: O(target)

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(result, candidates, target, new ArrayList<>(), 0);
        return result;
    }
    private void dfs(List<List<Integer>> result, int[] nums, int target, List<Integer> list, int start) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }
            list.add(nums[i]);
            dfs(result, nums, target - nums[i], list, i+1);
            list.remove(list.size()-1);
        }
    }
}

latest one

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        dfs(0, candidates, target, result, new ArrayList<>());
        return result;
    }
    private void dfs(int start, int[] candidates, int target, List<List<Integer>> result, List<Integer> list) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;
            }
            // System.out.println("i="+i);
            list.add(candidates[i]);
            dfs(i+1, candidates, target - candidates[i], result, list);
            list.remove(list.size()-1);
        }
    }
}

/**
sort and compare to previous the same elments, can avoid use the same number in an array 
        Arrays.sort(candidates);
        
        // compare to previous the same elments
        if (i > start && candidates[i] == candidates[i-1]) {

        thats why we need to sort first

        ex:
         a b c d e
        [1,1,1,1,1]
        target: 2

        [1]    




        2
        /
        1a--------------  first i is start, this will add to list(list.add(candidates[i]);), then dfs() , another condition keep running next for loop -> will check duplicated (i > start, && candidates[i] == candidates[i-1]) {
        / 
        1 [1,1,1,1] -> dfs part
        / use 1b
        0 -> get ans


so first time use 1a, then others in for loop because they are all the same (i > start, && candidates[i] == candidates[i-1]
so all skip

in next dfs, use 1b, then others in for loop all skip

-> result is [1,1]

sort and compare the same number continuousely
in this way to avoid duplicated combinations

T: O(2^n), choose or not chooes
S: O(n), worst case is to use all element, so dfs call stack deep is all elements -> is n


candidates = [2,5,2,1,2], target = 5

sort: 1,2,2,2,5
only will use the "first" one in each dfs call
ex: 2,2,2 -> use 2a and 2b
[1,2,2]

 */