1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), 1, n, k);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> curr, int pos, int n, int k) {
        if (curr.size() == k) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        for (int i = pos; i <= n; i++) {
            curr.add(i);
            helper(ans, curr, i + 1, n, k);
            curr.remove(curr.size() - 1);
        }
    }
}

还是挑数字当头部, 这次是挑够一定数量后就存到list中.

时间复杂度: Cnk, 从n个数字中挑k个有多少种挑发法.
空间复杂度: O(k) 因为最多决定k个位置, 此时栈的深度就是k. 这是不算存最后答案的空间的.