LeetCode LCR 080. 组合

2026-03-28 HGNULB 约 9 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 080. 组合

题意分析

输入两个整数 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，起点别写错；答案里每条组合的内部顺序题目不作要求，但按递增输出最自然也最便于自查。

解法：回溯枚举组合

核心思路

最朴素的想法是枚举 k 层嵌套循环，但 k 是运行时才知道的变量，循环层数写不出来，所以必须把「不定层数的嵌套循环」翻译成递归——这正是回溯的由来：递归深度充当循环层数，每层负责决定路径上的第 depth 个数。

直接递归的问题是重复。如果每层都从 1 到 n 随便选，[1, 2] 和 [2, 1] 会被当成两条不同路径产出，答案数从 $C(n, k)$ 膨胀到 $A(n, k)$，还得额外排序去重。瓶颈在于「同一组数字的不同排列被走了 k! 遍」。

观察在于：既然组合与顺序无关，那就人为规定一个顺序——只允许按严格递增的次序挑选。这样一组数字就只对应唯一一条搜索路径，重复被从根上掐掉。落到代码里就是给递归带一个参数 start，表示本层允许选择的最小数字；选中 num 之后，下一层从 num + 1 开始，保证路径上的数字严格递增。

由此得到第一条不变量：进入某层递归时，path 里的数字严格递增，且全部小于 start；因此本层从 start 起往后选，路径必然继续保持严格递增。递增序列与集合一一对应，所以每个组合恰好被产出一次，不重不漏。

第二个优化是剪枝上界。设当前 path 已有 path.size() 个数，还需要 need = k - path.size() 个。若本层选了 num，那么剩下可用的数字只有 num + 1 .. n 共 n - num 个，必须满足 n - num >= need - 1，整理得 num <= n - need + 1。也就是说循环上界不是 n 而是 n - need + 1，超过它的分支无论怎么往下走都凑不满 k 个数，提前砍掉能省下大量必然失败的递归。这就是第二条不变量：任何被真正进入的分支，剩余可选数字个数都足够填满剩余空位，因此递归树上不存在「走到底才发现凑不齐」的死路。

终止条件是 path.size() == k，此时把 path 的副本加入答案。之所以必须拷贝，是因为 path 是全程复用的同一个可变容器，回溯时会被不断增删；直接放引用的话，答案列表里塞的全是指向同一对象的指针，递归结束后 path 被清空，所有答案一起变空。

解题步骤

准备结果容器 res 和路径容器 path，从 backtrack(1, ...) 开始递归。起点是 1 而不是 0，因为题目的数字范围是 [1, n]。

每层进入时先判断 path.size() == k。达到长度就把 new ArrayList<>(path) 加入 res 并立刻 return，return 不能少，否则会继续往下选出超长路径。

计算 need = k - path.size()，即还差几个数。它是推导剪枝上界的唯一依据，写成变量比直接把表达式塞进循环条件更易读也更不易错。

循环 num 从 start 到 n - need + 1。上界的含义是「选了 num 之后，num 后面还剩至少 need - 1 个数」，保证这一支有希望凑满；若写成 n，答案仍然正确，只是会多走一堆注定失败的分支。

循环体内做「选择—递归—撤销」三步：path.add(num) 选中；backtrack(num + 1, ...) 递归，起点传 num + 1 而不是 start + 1，这是保证严格递增、避免重复的关键；path.remove(path.size() - 1) 撤销，把状态恢复成进入循环体之前的样子，供下一个 num 使用。

以 n = 4、k = 2 走一遍：初始 path = []，start = 1，need = 2，上界为 4 - 2 + 1 = 3，所以第一层只尝试 num = 1, 2, 3，num = 4 被剪掉——确实，首位选 4 之后已经没有更大的数可选了。

num = 1：path = [1]，递归 start = 2。此层 need = 1，上界为 4 - 1 + 1 = 4，尝试 num = 2, 3, 4，分别得到 [1,2]、[1,3]、[1,4] 三条答案。返回后撤销，path 回到 []。

num = 2：path = [2]，递归 start = 3，上界仍是 4，尝试 num = 3, 4，得到 [2,3]、[2,4]。注意这里不会再产生 [2,1]，因为起点已经被抬到 3。撤销后 path 回到 []。

num = 3：path = [3]，递归 start = 4，尝试 num = 4，得到 [3,4]。撤销后 path 回到 []。

第一层循环到 num = 3 结束，共产出 6 条答案 [1,2] [1,3] [1,4] [2,3] [2,4] [3,4]，恰好等于 $C(4, 2) = 6$，且每条内部递增、彼此互不相同。

代码实现

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

    private void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> res) {
        if (path.size() == k) {
            res.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, res);
            path.remove(path.size() - 1);
        }
    }
}

func combine(n int, k int) [][]int {
    res := make([][]int, 0)
    path := make([]int, 0, k)
    var dfs func(int)
    dfs = func(start int) {
        if len(path) == k {
            cur := append([]int(nil), path...)
            res = append(res, cur)
            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 res
}

复杂度分析

时间复杂度：$O(C(n, k) \cdot k)$。有了剪枝上界后，递归树上不存在注定失败的分支，每一条走到底的路径都对应一个合法组合，共 $C(n, k)$ 条；每条路径在终点处要把长度为 k 的 path 拷贝一份，故乘以 k。由于答案本身就有 $C(n, k) \cdot k$ 个整数要输出，这个量级已经触到问题下界。

空间复杂度：$O(k)$，不计返回值。递归深度最多 k 层，每层只有常数个局部变量；path 的长度也不超过 k。答案列表本身占 $O(C(n, k) \cdot k)$，属于必要输出，通常不计入额外空间。

关键点总结

组合去重的手段是「人为规定递增次序」，靠 start 参数实现；递归时传 num + 1 而不是 start + 1，这是模板里最容易写错的一处。

剪枝上界 n - need + 1 由「剩余数字数 ≥ 剩余空位数」推导而来，能背下结论，但面试里最好现场推一遍，说明它砍掉的是必然失败的分支而非合法解。

收集答案必须深拷贝，path 是复用的可变容器，直接放引用会让所有答案指向同一个对象。

「选择—递归—撤销」三步要严格配对，撤销漏写会让路径越积越长，多写会让状态提前失效。

面试视角：本题是回溯三大类（组合、排列、子集）的入口，回答时最好主动区分——组合用 start 防重复，排列用 used 数组标记已选，子集则是在每个节点而非只在叶子处收集答案。能讲清这三者的差异，比写出单个模板更有价值。

面试视角：常见追问是「若原数组含重复元素怎么办」，答案是先排序，再在同一层循环里跳过与前一个相同的数字（i > start && nums[i] == nums[i-1] then continue），这就是 40 题的做法；另一个追问是「能否非递归实现」，可以提字典序法或二进制枚举，但要指出后者在 n 较大时不适用。

易错点总结

错误写法：收集答案时直接 res.add(path)，不做拷贝 → 用 n = 4、k = 2 时，res 里 6 个元素全是同一个 path 对象的引用，递归彻底结束后 path 已被回溯清空，最终输出 6 个空列表；Go 里写成 res = append(res, path) 同理，底层数组共享，后续 append 会互相覆盖。

错误写法：递归时传 backtrack(start + 1, ...) 而不是 num + 1 → 用 n = 4、k = 2 时，第一层选 num = 2 后下一层仍从 2 开始，会产出 [2, 2] 这种含重复元素的非法组合。

错误写法：递归时传 start 不变 → 用 n = 4、k = 2 时会产出 [1,1]、[1,2]、[2,1] 等，既有重复元素又有同组的不同排列，答案数远超 6。

错误写法：命中 path.size() == k 后忘记 return → 用 n = 4、k = 2 时，[1,2] 被收集后继续往下选，need 变成 0，循环上界成了 n + 1，num 会取到 5，路径长度超过 k 且再也不会被收集，白白浪费大量递归。

错误写法：漏写 path.remove(path.size() - 1) → 用 n = 4、k = 2 时，收完 [1,2] 返回后 path 仍是 [1,2]，接着又追加 3，长度一路只增不减，path.size() == k 再也不成立，除了第一条之外的答案全部丢失。

错误写法：把循环上界写成 num < n → 用 n = 4、k = 2 时 num 最大只到 3，第二层选不到 4，[1,4]、[2,4]、[3,4] 三条答案全部丢失。

错误写法：剪枝上界写成 n - k + 1（用 k 而不是 need）→ 用 n = 4、k = 2 时每层上界都被压成 3，第二层选不到 4，同样丢掉三条答案；正确的上界必须随已选个数动态变化。

错误写法：起点从 0 开始递归 backtrack(0, ...) → 用 n = 4、k = 2 时会产出含 0 的组合如 [0, 1]，而题目要求数字取自 [1, n]。

错误写法：Go 里写 cur := path 之后 res = append(res, cur) → 切片是引用语义，cur 与 path 共用底层数组，后续回溯的 append 会就地改写已收集的答案，输出全乱；必须显式 append([]int(nil), path...) 复制一份。

错误写法：为了「去重」先枚举全排列再用集合过滤 → 用 n = 20、k = 10 时排列数是组合数的 $10!$ 倍，约 6.6 亿条，必然超时；去重应该靠搜索结构而非事后过滤。

相似题目

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