77. 组合

1. 题目

给定两个整数 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]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n

2. 思路

  • 已知题目要求获取到所有的排列组合，同时结果集内的数字不限制顺序，但结果集出现的数字频率必须是唯一的
  • 根据题目，可以很快的确定出该题需要用到回溯的方式进行暴力搜索得到所有的集合，其中回溯法的模板为以下：
1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
  • 当回溯的过程中，发现临时数组集合中的元素数量已达到k个，则将该临时数组写入结果集合中
  • 回溯时，需要注意的是，假设n为3，k为2，当首次已遍历1, 2，第二次遍历时则无需再遍历2, 1，因为两个数组其实是一样的
  • 以上可以通过回溯参数递增的index进行规避，通过控制循环中每次初始化的num = index + 1来规避掉已经被遍历组合过的数
  • 回溯过后的撤销处理结果则可以通过list.remove(list.size() - 1)来处理

3. 代码

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

        dfs(n, k, 0, new ArrayList<Integer>(), result);

        return result;
    }

    private void dfs(int totalNums, int totalSize, int index, List<Integer> list, List<List<Integer>> result) {
        if (list.size() == totalSize) {
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for (var num = index + 1; num <= totalNums; ++num) {
            list.add(num);
            dfs(totalNums, totalSize, num, list, result);
            list.remove(list.size() - 1);
        }
    }
}

4. 复杂度

  • 时间复杂度：O(n ^ k)
  • 空间复杂度：O(k)，主要是递归栈的空间复杂度

image-20231222123746553