LeetCode 77. 组合

◎

本节目标

用 start 固定递增选择顺序，并按还缺少的元素数量提前收缩搜索范围。

这道题在回溯决策树中把子集模板加上长度目标：从 1 到 n 选出恰好 k 个数。

查看 LeetCode 原题

题意与约束

返回 [1, n] 中所有长度为 k 的组合。组合内部按递增顺序记录，选择 {1, 3} 后不再生成 {3, 1}。

朴素思路与瓶颈

先枚举全部 2^n 个子集，再筛选长度为 k，会走过大量不可能成为答案的节点。递归路径一旦已经有 k 个数字就可收集；如果剩余可选数字不足以补满长度，也无需进入该分支。

start 与剩余数量剪枝

start 表示本层可选择的最小数，递归到下一层时传入 value + 1，所以路径严格递增。若当前路径还缺 need = k - path.size() 个数，本层起始值最多只能到 n - need + 1；再大的起点后面没有足够数字填满路径。

这个上界不会改变结果，只是在递归前删除必然失败的分支。路径达到长度 k 时复制到答案，不能继续添加数字。

代码实现

C++

C++17

#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<int>> answer;
    vector<int> path;

    void backtrack(int n, int k, int start) {
        if (static_cast<int>(path.size()) == k) {
            answer.push_back(path);
            return;
        }

        int need = k - static_cast<int>(path.size());
        for (int value = start; value <= n - need + 1; value++) {
            path.push_back(value);
            backtrack(n, k, value + 1);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combine(int n, int k) {
        answer.clear();
        path.clear();
        backtrack(n, k, 1);
        return answer;
    }
};

Python

Python 3

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        answer: list[list[int]] = []
        path: list[int] = []

        def backtrack(start: int) -> None:
            if len(path) == k:
                answer.append(path.copy())
                return

            need = k - len(path)
            for value in range(start, n - need + 2):
                path.append(value)
                backtrack(value + 1)
                path.pop()

        backtrack(1)
        return answer

复杂度分析

答案数为组合数 C(n, k)，每个答案需要复制 k 个整数，时间复杂度为 O(k · C(n, k))。递归栈和当前路径额外占用 O(k) 空间，输出答案占用 O(k · C(n, k)) 空间。

易错点

• 下一层从 value 而非 value + 1 开始，错误地允许同一个数字重复出现。
• 循环写到 n，却没有考虑剩余数字数量，徒增不可能补满的递归。
• 到达长度 k 后仍继续枚举，得到长度超过 k 的路径。

模式迁移

固定长度的选数、从候选列表中选若干元素和组合型字符串构造都可使用相同的 start 边界。候选值可以重复使用时，下一层传当前下标而不是下标加一，这正是下一题的差异。