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

Combinations - LeetCodeLeetCode

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

所以最新的做法是:

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

時間複雜度跟 subset 一樣

time: O(2^n) or O(2^n*n) , the subset's count is 2^n

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

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!

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

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);
        }
    }
}