LeetCode 77. 组合

约 5 分钟
文章信息 13 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 腾讯 京东 拼多多 商汤 虾皮 面试经典 150 题
标签
回溯 回溯经典题 组合问题
目录

题目描述

✅ 77. 组合

image-20250419034138034

题意分析

输入两个整数 n 和 k，要输出从 1 到 n 这 n 个数中选出 k 个数的所有组合，答案可以按任意顺序返回。

约束里最关键的信号是「组合」二字：[1, 2] 和 [2, 1] 被视为同一个答案，只能出现一次。这与排列题的根本区别，决定了枚举方式必须能天然规避重复，而不是先枚举全部排列再去重。另一个信号是 1 <= k <= n <= 20，答案数量是 $C(n, k)$，最大出现在 n = 20、k = 10 时约 18 万条，规模上允许把每一条答案都真正构造出来，也就是说这是一道「输出全部方案」的枚举题，不存在比枚举更快的算法——下界就摆在答案个数上。

边界上要考虑：k 等于 n 时答案只有一条，就是全选；k 等于 1 时答案有 n 条；数字范围从 1 开始而不是 0，起点别写错；答案里每条组合的内部顺序题目不作要求，但按递增输出最自然也最便于自查。

解法：回溯枚举组合

核心思路

组合只关心选了哪些数，不关心顺序。若每层都从 1 开始选择，[1,2] 和 [2,1] 会重复出现。解决方法是让路径始终严格递增：递归参数 start 表示本层可选的最小数字，选择 num 后，下一层只从 num+1 继续。

循环不变量是：进入递归时，path 严格递增，且其中所有数都小于 start。因此每个组合只对应唯一一条递归路径，既不重复也不遗漏。路径长度达到 k 时，必须复制当前路径加入答案，因为后续回溯还会修改原容器。

还可以剪掉必然凑不满的分支。若当前还需要 need = k - path.size() 个数，本层选择的 num 后面至少要剩下 need-1 个数：

\[n-num \ge need-1 \quad\Longrightarrow\quad num \le n-need+1\]

所以本层循环上界是 n-need+1，而不是 n。

解题步骤

  1. 从 start=1、空路径开始递归。
  2. 当路径长度等于 k 时，复制路径加入答案并返回。
  3. 计算还需选择的数量 need，只枚举 start..n-need+1。
  4. 对每个 num 执行“加入路径 → 从 num+1 递归 → 删除路径末尾”。

以 n=4, k=2 为例，第一层还需 2 个数，上界为 4-2+1=3，所以不会尝试 4 作为首元素；选择 1 后，下一层从 2 开始，依次得到 [1,2]、[1,3]、[1,4]，其余分支同理，共得到 6 个组合。

代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(), ans);
        return ans;
    }

    private void backtrack(int start, int n, int k,
                           List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }

        int need = k - path.size();
        for (int num = start; num <= n - need + 1; num++) {
            path.add(num);
            backtrack(num + 1, n, k, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

func combine(n int, k int) [][]int {
    ans := make([][]int, 0)
    path := make([]int, 0, k)

    var dfs func(int)
    dfs = func(start int) {
        if len(path) == k {
            ans = append(ans, append([]int(nil), path...))
            return
        }

        need := k - len(path)
        for num := start; num <= n-need+1; num++ {
            path = append(path, num)
            dfs(num + 1)
            path = path[:len(path)-1]
        }
    }

    dfs(1)
    return ans
}

复杂度分析

  • 时间复杂度：$O\left(k\binom{n}{k}\right)$。共有 $\binom{n}{k}$ 个答案，每个答案复制 k 个元素；这也是输出本身的下界。
  • 空间复杂度：不计返回结果为 $O(k)$，用于递归栈和当前路径；结果占 $O\left(k\binom{n}{k}\right)$。

关键点总结

  • start 保证路径递增，从搜索结构上消除组合的顺序重复。
  • 剪枝上界 n-need+1 来自“剩余数字必须足够填满路径”，应会现场推导。
  • 记录答案时要深拷贝；Java 的列表和 Go 的切片都不能直接复用。
  • 回溯的三个动作必须成对：选择、递归、撤销。

易错点总结

  • 下一层传 start+1 而不是 num+1：会产生重复数字或重复组合。
  • 收集答案时不复制 path：后续回溯会覆盖已经保存的结果。
  • 剪枝上界写成固定的 n-k+1：越往深层仍用旧上界，会漏掉包含末尾数字的组合。
  • 忘记撤销最后一次选择：不同分支会共享错误的路径状态。

相似题目

题目 难度 考察点
39. 组合总和 中等 同一元素可重复选取
40. 组合总和 II 中等 含重复元素时的同层去重
216. 组合总和 III 中等 个数与和的双重约束剪枝
78. 子集 中等 在每个节点而非叶子收集答案
46. 全排列 中等 用 used 标记而非 start 控制
17. 电话号码的字母组合 中等 多个候选集合的逐层展开
LCR 080. 组合 中等 同题换皮的模板默写