LeetCode LCR 080. 组合

约 4 分钟
文章信息 5 个分类 3 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 LCR 回溯

题目描述

✅ LCR 080. 组合

image-20260929005846786

image-20260929005846790

题意分析

从整数 1..n 中选出 k 个不同的数，返回所有组合。同一组数的不同排列只算一个答案，可以按任意顺序返回各个组合。

解法：按剩余数量剪枝的组合回溯

核心思路

[!blue]

每个组合都有唯一的递增排列，因此只沿着数值递增的方向选择。用 start 表示本层可选的最小数字，选中 num 后，下一层从 num + 1 开始。这样每个数最多选一次，也不会重复输出同一组数的其他排列。

path 保存已经选中的数，长度达到 k 时保存副本并返回。返回上一层后撤销末项，让后续分支继续使用原来的路径。

还可以提前排除凑不满数量的分支。当前还需要 need = k - path.size() 个数，若本层选择 num，后面只剩 n - num 个更大的数，必须满足 n - num >= need - 1，即 num <= n - need + 1。超过这个上界一定无解，所以循环不必走到 n。

解题步骤

  1. 创建结果和空路径，从 start = 1 开始。
  2. 路径长度等于 k 时，保存路径副本并返回。
  3. 计算剩余所需数量 need，枚举 start..n - need + 1。
  4. 追加当前数字 num，递归处理 num + 1 开始的候选。
  5. 递归返回后删除路径末项，继续本层枚举。

代码实现

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(k\binom{n}{k})$。剪枝后的每个分支都能扩展成合法组合，共有 $\binom{n}{k}$ 个结果，每个结果复制 k 个数；搜索开销也被这些完整路径的总长度覆盖。
  • 空间复杂度：不计结果为 $O(k)$，用于路径与递归栈；结果占 $O(k\binom{n}{k})$。

关键点总结

[!green]

  • 严格递增的选择顺序与组合一一对应，无需事后去重。
  • 上界由剩余数量推导，只剪掉必然凑不满的分支。
  • k = n 时只会沿全选路径前进；k = 1 时每个数单独形成一个答案。

易错点总结

[!yellow]

  • 初始数字从 1 开始，下一层起点是本次选择的 num + 1，不是原来的 start + 1。
  • 剪枝上界是 n - need + 1，少了 1 会漏掉恰好能选满的分支。
  • 路径长度达到 k 就保存副本并返回，不能继续生成更长路径。
  • 递归返回后撤销最后一次选择，避免兄弟分支共享残留状态。

相似题目

题目 难度 关联与区别
78. 子集 中等 原题枚举全部大小的子集，本题只收集恰好k个元素的选择。
216. 组合总和 III 中等 同样固定组合大小，再额外限制元素和，可结合剩余数量与和的边界剪枝。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/99345020
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！