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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MiC2MQwPWlbviLhOpVw%2F-MiC2XvF38043RVB55St%2Fimage.png?alt=media\&token=04259497-c7a0-4130-b79e-997276ec6793)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MiC2MQwPWlbviLhOpVw%2F-MiC2a-EQHMkZemoXWzm%2Fimage.png?alt=media\&token=b0db7698-0eca-476b-a7b1-85aeaedd3e3d)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MiC2MQwPWlbviLhOpVw%2F-MiC2d3J4-5x-QDWDe_V%2Fimage.png?alt=media\&token=8f3b70eb-24bf-455e-a4de-c0cae6565841)





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

space: O(target)

```java
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]**

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MiC7zjixr-5KBBiGHyc%2F-MiC9bRVa4kNetaWnuMg%2Fimage.png?alt=media\&token=411f0af4-21b0-42ed-8392-d17b97a72b65)



![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MiC7zjixr-5KBBiGHyc%2F-MiC83BUb_dKTive3Yu9%2Fimage.png?alt=media\&token=1e74c08e-f120-4e76-9133-4545ddf48ce7)

```java
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 的順序是對的, 就不會有重複問題

因為可以保![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FU4AFuvV0031urvXdBK8X%2Fimage.png?alt=media\&token=2eb444ee-6357-45da-8224-8572be5dcbf0)證 2  在前面

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

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

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

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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F1WOvhlbSEUexlTiQsQPP%2Fimage.png?alt=media\&token=899d6714-7969-40c5-895c-af4052c4219c)



如果用 i = 0&#x20;

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

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

&#x20;          &#x20;

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FLVQwTBFAdiTtFirXKRH3%2Fimage.png?alt=media\&token=396b6ec1-c9fa-4be6-9558-b7518588768d)

&#x20;             5  .      4       1  . 0                                     4

&#x20;      -2  . -3                                                           -2

&#x20;3 2 x  x     2  => -2 => \[2,3,2]                              2 => -2 => \[3,2,2]

.-2 => \[2,2,3]&#x20;

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

&#x20;
