LC.P77[组合]

思路：回溯 + 剪枝

方法一：枚举下一个数选哪个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int k;

    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        dfs(n);
        return ans;
    }

    private void dfs(int i) {
        int d = k - path.size(); // 还要选d个数
        if (d == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j >= d; --j) {
            path.add(j);
            dfs(j - 1);
            path.remove(path.size() - 1);
        }
    }
}
  • 时间复杂度：分析回溯问题的时间复杂度，通用公式为：路径长度$ × $搜索树的叶子数。对于本题，为$O(k * C^k_n)$
  • 空间复杂度：$O(k)$

方法二：选或不选

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int k;

    public List<List<Integer>> combine(int n, int k) {
        this.k = k;
        dfs(n);
        return ans;
    }

    private void dfs(int i) {
        int d = k - path.size();
        if (d == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 不选
        if (i > d) dfs(i - 1);

        // 选
        path.add(i);
        dfs(i - 1);
        path.remove(path.size() - 1);
    }
}