39. Combination Sum (not use befroe, so int I = start, dfs(i) -> is i !!

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

space: O(target)

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res, new ArrayList<>(), candidates, target, 0);
        return res;
    }
    
    private void helper(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int start) {
        if (target < 0) {
            return;
        } else if (target == 0) {
            res.add(new ArrayList<>(list));
        } else {
            for (int i = start; i < candidates.length; i++) {
                list.add(candidates[i]);
                helper(res, list, candidates, target - candidates[i], i); // pass i, why i = start => for seq search
                list.remove(list.size()-1);
            }
        }
        
    }
}

/*

7 - any of [],

7 = [2,3,6,7]

7 - 2 = 5

5 - 2 = 3

3 - 2 => no, 3 - 3 ok! backtrack



*/

why we cant just use for (i = 0..., because it should pass "the current index

and pass i, means we can reuse the same number

backtracking, we always have a tree (ex: [2, 3, 6, 7]), then cut and find the ans.

[2, 3, 6, 7]

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, candidates, target, new ArrayList<>(), 0);
        return result;
    }
    private void dfs(List<List<Integer>> result, int[] candidates, int target, List<Integer> list, int start) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        // if every time from i = 0, will generate like [2,2,3] [2,3,2], [3,2,2]
        // just use order seq to pass the i index
        for (int i = start; i < candidates.length; i++) {
            list.add(candidates[i]);
            dfs(result, candidates, target - candidates[i], list, i);
            list.remove(list.size()-1);
        }
    }
}

想要避免這種狀況, 記得 use i = start, 並且傳入 i, 這樣可以保證傳入 i 的順序是對的, 就不會有重複問題

會持續先用 2 來 try, 直到不行再開始退回 (所以也是為什麼 < target 要 return), 像這個最左邊的例子

當然 target == 0 時就會紀錄下來結果

2都 try 過多次後, 到最左邊的 -1 了, 退回, 才會開始用 3 來 try （所以分支就從-3 開始用了, -2 就不會在用了

所以這樣就能保證都先用 2 在用 3... 所以可以得到 [2,2,3]

如果用 i = 0

結果 [2,2,3] [2,3,2], [3,2,2] =>  如果用 i = 0, 會

就是每次固定都用 4個分支去 try

5 . 4 1 . 0 4

-2 . -3 -2

3 2 x x 2 => -2 => [2,3,2] 2 => -2 => [3,2,2]

.-2 => [2,2,3]

這樣得到就是會其實有重複

PreviousPage 9 Next78. Subsets (not use befroe, so int I = start, dfs(i+1)

Last updated 3 years ago

Was this helpful?

class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); helper(res, new ArrayList<>(), candidates, target, 0); return res; } private void helper(List<List<Integer>> res, List<Integer> list, int[] candidates, int target, int start) { if (target < 0) { return; } else if (target == 0) { res.add(new ArrayList<>(list)); } else { for (int i = start; i < candidates.length; i++) { list.add(candidates[i]); helper(res, list, candidates, target - candidates[i], i); // pass i, why i = start => for seq search list.remove(list.size()-1); } } } } /* 7 - any of [], 7 = [2,3,6,7] 7 - 2 = 5 5 - 2 = 3 3 - 2 => no, 3 - 3 ok! backtrack */

class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<>(); dfs(result, candidates, target, new ArrayList<>(), 0); return result; } private void dfs(List<List<Integer>> result, int[] candidates, int target, List<Integer> list, int start) { if (target < 0) { return; } if (target == 0) { result.add(new ArrayList<>(list)); return; } // if every time from i = 0, will generate like [2,2,3] [2,3,2], [3,2,2] // just use order seq to pass the i index for (int i = start; i < candidates.length; i++) { list.add(candidates[i]); dfs(result, candidates, target - candidates[i], list, i); list.remove(list.size()-1); } } }