77.组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

1
2
输入：n = 1, k = 1
输出：[[1]]

这里在常规的回溯方法上加了剪枝操作，在判断出最后的可选字符无法满足组合字符个数的前提下，直接返回

Solution：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    // ans用来存储所有可能的组合结果，每个组合都是一个整数列表
    private final List<List<Integer>> ans = new ArrayList<>();
    
    // path用来记录当前递归路径上选择的整数，它代表了一个具体的组合
    private final List<Integer> path = new ArrayList<>();
    
    // k是组合中需要选择的整数数量
    private int k;

    // combine方法是公有方法，用于启动组合生成过程，并返回所有可能的组合
    public List<List<Integer>> combine(int n, int k) {
      // 初始化k
      this.k = k;
      // 从n开始进行深度优先搜索（DFS）
      dfs(n);
      // 返回所有组合的列表
      return ans;
    }

    // dfs方法是一个私有方法，用于递归地构建组合
    private void dfs(int i) {
        int d=k-path.size();
        // 当前路径长度等于k时，说明找到了一个有效组合，将其添加到结果列表中
        if (path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }

        // 递归地在剩余的数字中选择下一个数字加入到当前组合`path`中
         for (int j = i; j > d-1; j--) {
        
            path.add(j);
            dfs(j-1);
            path.remove(path.size()-1);

        }
    }
}