LeetCode 22. 括号生成

◎

本节目标

在构造过程中维护左右括号计数，只扩展仍可能成为合法序列的前缀。

这道题在回溯决策树中加入前缀约束：不先生成全部括号串再筛选，而是从一开始就拒绝不可能合法的分支。

查看 LeetCode 原题

题意与约束

给定 n 对括号，生成所有格式正确的括号组合。任何前缀中，右括号数量都不能超过左括号数量；最终左右括号数量都必须为 n。

朴素思路与瓶颈

长度为 2n 的每个位置都选左或右括号会产生 2^(2n) 条字符串，其中绝大多数在很早的前缀就已经非法。事后用栈检查只能验证结果，无法避免这些无效搜索。

计数约束就是剪枝

状态记录已放入的 open 和 close 数量。若 open < n，仍能加入左括号；若 close < open，才允许加入右括号。后一条件确保任何时刻右括号都没有超过左括号，因此非法前缀永远不会进入递归树。

路径长度达到 2n 时，两类括号都已经用满，当前字符串就是一个合法答案。每次加入字符后都要在返回时删除它，让另一种选择从同一前缀开始。

代码实现

C++

C++17

#include <string>
#include <vector>

using namespace std;

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

    void backtrack(int n, int open, int close) {
        if (static_cast<int>(path.size()) == n * 2) {
            answer.push_back(path);
            return;
        }

        if (open < n) {
            path.push_back('(');
            backtrack(n, open + 1, close);
            path.pop_back();
        }
        if (close < open) {
            path.push_back(')');
            backtrack(n, open, close + 1);
            path.pop_back();
        }
    }

public:
    vector<string> generateParenthesis(int n) {
        answer.clear();
        path.clear();
        backtrack(n, 0, 0);
        return answer;
    }
};

Python

Python 3

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

        def backtrack(open_count: int, close_count: int) -> None:
            if len(path) == n * 2:
                answer.append(''.join(path))
                return

            if open_count < n:
                path.append('(')
                backtrack(open_count + 1, close_count)
                path.pop()
            if close_count < open_count:
                path.append(')')
                backtrack(open_count, close_count + 1)
                path.pop()

        backtrack(0, 0)
        return answer

复杂度分析

合法结果数为第 n 个 Catalan 数 C_n。每个结果长度为 2n，构造与复制答案的时间复杂度为 O(n · C_n)。递归栈和路径额外使用 O(n) 空间，输出空间为 O(n · C_n)。

易错点

• 只限制左括号数量，没有限制 close < open，会生成以右括号开头的非法前缀。
• 条件写成 close <= open，允许左右数量相等时继续加入右括号。
• 路径达到长度后未立即返回，继续递归会超过 n 对括号。

模式迁移

其他带前缀合法性的构造题也应把可检查约束放到递归前：例如生成受限二进制串、满足容量上限的选择序列，或需要同时维护多类计数的调度方案。越早排除不合法分支，搜索树越小。