# 77. Combinations (not use before, so int I = start, dfs(i+1

{% embed url="<https://leetcode.com/problems/combinations>" %}

其實就是求 subset 的某一層, ex c3取2 => 就是 subset 的 level 2

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F9nEoAiLa54ZlmNfZnvCi%2Fimage.png?alt=media\&token=9d2f2034-30e8-4398-92c5-3c2958069a3d)

所以最新的做法是:

但這做法會探索所有可能, 所以比較慢, 但比較好記...

時間複雜度跟 subset 一樣

time: O(2^n) or O(2^n\*n) , the subset's count is 2^n &#x20;

space: O(2^n) or O(2^n\*n)

```java
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(n, k, result, new ArrayList<>(), 1);
        return result;
    }
    private void dfs(int n, int k, List<List<Integer>> result, List<Integer> list, int start) {
        if (list.size() == k) {
            result.add(new ArrayList<>(list));
        }
        for (int i = start; i <= n; i++) {
            list.add(i);
            dfs(n, k, result, list, i+1);
            list.remove(list.size()-1);
        }
    }
}
```

why  i  <= n - k + 1

For anyone stumped by why this change is necessary, it's because you should not continue exploring (recursing) when you know that there won't be enough numbers left until `n` to fill the needed `k` slots. **If n = 10, k = 5, and you're in the outermost level of recursion, you choose only i = 1...6 , because if you pick i=7 and go into `backTracking()` you only have 8,9,10 to pick from, so at most you will get \[7,8,9,10]... but we need 5 elements!**

```java

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), 1, n, k);
        return result;
    }
    
    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int start, int n, int k) {
        if (k == 0) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = start; i <= n-k+1; i++) {
                tempList.add(i);
                backtrack(result, tempList, i+1, n, k - 1);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}
```

time: O( k\*c(n, k))

space: O( k\*c(n, k))

use <= n

```java
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        // use backtracking
        //   1,     2,    3,   4   k=2
        // 2 3 4   3. 4   4
        List<List<Integer>> res = new ArrayList<>();
        helper(res, new ArrayList<>(), n, k, 1);
        return res;
        
    }
    private void helper(List<List<Integer>> res, List<Integer> list, int n, int k, int start) {
        if (k == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i <= n; i++) {
            list.add(i);
            helper(res, list, n, k-1, i + 1);
            list.remove(list.size()-1);
        }
    }
}
```