BM60　括号生成¶

中等通过率 51.69%python3核心代码模式样例通过牛客 AC递归

牛客原题　源码

讲解章节：DFS 深度优先搜索

一句话

逐位填 '(' 或 ')'，靠「左括号不超 n、右括号不超左括号」两条规则保证合法。

解题思路¶

这题考什么¶

先枚举全部 2^(2n) 种串再验证合法性太浪费，正确做法是边生成边保证合法，让搜索树上根本长不出非法分支。

一个括号串合法，等价于：任意前缀里右括号数不超过左括号数，且最终两者都等于 n。把这句话直接翻译成回溯的两条放子规则，只用记左右各已用了几个：

放 '('：当且仅当 left  < n         —— 左括号还有存货
放 ')'：当且仅当 right < left      —— 有未闭合的左括号可以配对

第二条是核心：right < left 保证了任何时刻的前缀里右括号都不会超过左括号，因此走到 left == right == n 时得到的一定是合法串，无需额外校验。这两条既充分也必要——任何合法串都能被这套规则生成，所以不重不漏。

n=2 的搜索树（括号内是 left/right）
    (        (1,0)
    ((       (2,0) -> (())
    ()       (1,1) -> ()()

数据规模与复杂度¶

0 <= n <= 10，时限「其他语言 2 秒」。合法串的个数是第 n 个卡特兰数， n=10 时是 16796 个，每个长 20 个字符。由于每个搜索节点都至少通向一个合法解，总代价与结果规模同阶，写作 O(4^n / sqrt(n))（卡特兰数的渐近式）。空间 O(n)：递归深度是 2n，路径列表最长 2n，不计结果本身。「先枚举 2^20 = 1048576 个串再逐个验证」也能在时限内跑完 n=10，但其中 98% 的分支是白跑的，n 再大一点就彻底崩掉。

坑在哪¶

right < left 写成 right <= left 会立刻生成 "())" 这类右括号超前的串，而且这种错串不会在终止条件处被拦下——终止只数个数，不数顺序。
终止条件用 left == n and right == n。只判 left == n 会在右括号还没补齐时就收下半成品；只判路径长度 2n 也对，但需要额外的长度计算。
两个分支是并列的 if，不是 if/else：同一个状态下往往两种括号都能放，写成 else 会砍掉一半解（n=2 时只剩 "(())"）。
path 用列表累积、回溯时 pop：字符串是不可变对象，每层拼接都要复制一份，深度 2n 的路径上会产生 O(n) 份中间串。
n = 0 时首次调用就命中终止条件，返回 [""]——一个含空串的列表，不是空列表。

样例复核¶

n=2 时，先放 '(' 到 (1,0)：再放 '(' 得 (2,0)，此后只能连放两个 ')'，出 "(())"；退回 (1,0) 改放 ')' 得 (1,1)，再放 '(' 与 ')' 出 "()()"。共两个串，与示例 2 一致。

参考实现¶

solutions/nowcoder/BM60/sol.py
from typing import List, Optional


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

        # 状态只需两个计数：已用的左括号数与右括号数，前缀是什么串不影响后续决策
        def build(left: int, right: int) -> None:
            # 两种括号都用满 n 个才算一个解；此处不必再校验合法性，规则已保证
            if left == n and right == n:
                res.append("".join(path))
                return
            if left < n:                 # 左括号还没用完，随时可以放
                path.append("(")
                build(left + 1, right)
                path.pop()
            # 与上一段是并列的 if 而非 else：同一状态下两种括号常常都能放
            if right < left:             # 只有存在未闭合的左括号时才允许放右括号
                path.append(")")
                build(left, right + 1)
                path.pop()

        build(0, 0)
        return res

BM60 括号生成¶