LC22　括号生成¶

中等通过率 79%python3核心代码模式回溯样例通过牛客 AC字符串动态规划回溯括号序列

一句话

逐个字符往下填，靠「左括号不超 n、右括号不超左括号」两条剪枝只走合法分支。

解题思路¶

这题考什么¶

暴力做法是枚举全部 2 的 2n 次方个长度为 2n 的括号串再逐个验证， n = 8 时是 6.5e4 条串乘上验证开销，而合法的只有卡特兰数 C(8) = 1430 条，绝大部分工作被浪费在必然不合法的分支上。

换成边填边判：一个括号串合法，等价于 (a) 左括号与右括号各恰好 n 个； (b) 任意前缀里右括号数不超过左括号数（否则某个右括号找不到配对的左括号）。于是在第 k 个位置上只有两种选择，各配一条剪枝：填 '('：要求已填左括号数 open < n，否则左括号会超额；填 ')'：要求 close < open，否则这个右括号立刻违反 (b)。两条剪枝把搜索树砍成「只长出合法前缀」的形状，走到长度 2n 的叶子必定是一个合法解，收答案时不需要再验证——合法性由不变量沿途保证。

n = 2 的搜索树（括号内是 open,close）
    ""(0,0) -> "("(1,0) -> "(("(2,0) -> "(()"(2,1) -> "(())"
                        -> "()"(1,1) -> "()("(2,1) -> "()()"

回溯的「选择 -> 递归 -> 撤销」三步见 DFS 深度优先搜索。

数据规模与复杂度¶

1 <= n <= 8。合法串的条数是第 n 个卡特兰数，n = 8 时为 1430。剪枝后搜索树的叶子与答案一一对应，内部结点数是同一量级，每条答案再花 O(n) 拼串，时间 O(n 乘卡特兰数(n))，n = 8 时约 2e4 次基本操作。空间 O(n)：path 与递归栈都只有 2n = 16 层。

坑在哪¶

两条剪枝的条件不对称，别写成同一个模子。左括号看的是与上界 n 比（open < n），右括号看的是与当前左括号数比（close < open）。把后者误写成 close < n，会放出 "))((" 这类前缀非法的串。
出口用「已填长度达到 2n」判断即可，不必再检查 open == close == n：两条剪枝保证了 open <= n 且 close <= open，长度到 2n 时只能是各 n 个。多写一层判断不算错，但会让人误以为剪枝不完备。
收答案要 "".join(path) 生成新串。path 是全程复用的列表，直接存 path 本身的话，回溯结束时它已被弹空，输出会变成一堆空列表。
每个 append 都要有配对的 pop，且必须写在递归之后。漏掉任何一处撤销，兄弟分支就会带着上一条分支的残留字符继续往下填。
本题走严格比对，_judge.json 里没有给它配 unordered。所以产出顺序必须与力扣官方一致。本文件的枚举顺序是「先试 '(' 再试 ')'」，等价于把 '(' 看作比 ')' 小的字典序，恰好就是官方样例的排列顺序。两个分支写反，n = 3 的第一条会变成 "()()()"，整份输出都对不上。

样例复核¶

n = 3 按「先 '(' 后 ')'」产出：((()))、(()())、(())()、()(())、()()()，共 5 条 = 卡特兰数 C(3)，与样例逐条一致。

参考实现¶

solutions/leetcode/LC22/sol.py
from typing import List, Optional


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # res 收答案，path 是当前正在填的括号串（按字符存）
        res = []
        path = []

        def dfs(open_cnt: int, close_cnt: int) -> None:
            # 长度到 2n 即收工：两条剪枝已保证 open <= n 且 close <= open，此刻必是各 n 个
            if len(path) == 2 * n:
                res.append("".join(path))
                return
            # 先试 '(' 再试 ')'，等价于把 '(' 当作较小的字符，产出即官方给的顺序
            if open_cnt < n:
                # 剪枝一：左括号总数不能超过 n，否则右边凑不够配对
                path.append("(")
                dfs(open_cnt + 1, close_cnt)
                path.pop()          # 撤销，让这一位改填 ')'
            if close_cnt < open_cnt:
                # 剪枝二：右括号数不能超过已有的左括号数，否则这个 ')' 当场无人配对
                path.append(")")
                dfs(open_cnt, close_cnt + 1)
                path.pop()          # 撤销，回到上一层重新决定

        dfs(0, 0)
        return res

LC22 括号生成¶