22. 括号生成

LeetCode 22¹ · 中等 · 回溯

题

给整数 n，生成所有由 n 对括号组成的有效括号串，顺序任意。

例：n = 3 → ["((()))","(()())","(())()","()(())","()()()"]。

一句话

边生成边保证前缀合法——open < n 才放 (，close < open 才放 )，走到长度 \(2n\) 的每条路径都是答案，不用事后校验。

关键技巧

合法括号串的判定 = 前缀里右括号永远不多于左括号，且最终相等。 把这个判定拆成两条局部规则挂在每次选择上：

• 放 ( 的前提：open < n（总共只有 \(n\) 个）；
• 放 ) 的前提：close < open（放完后前缀仍然合法）。

为什么对。 两条规则维持不变量 \(close \le open \le n\)。长度到 \(2n\) 时必有 \(open = close = n\)，且每个前缀都满足 \(close \le open\)——正是合法串的定义。反过来，任何合法串的每一步都满足这两条，所以一个不漏。

比暴力好在哪。 暴力枚举 \(2^{2n}\) 个串再逐一检查；剪枝后只走合法前缀，叶子数就是答案数——第 \(n\) 个 Catalan 数 \(C_n = \frac{1}{n+1}\binom{2n}{n} \sim \frac{4^n}{n^{3/2}}\)。

解

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

        def dfs(open_, close):
            if len(path) == 2 * n:
                res.append("".join(path))
                return
            if open_ < n:
                path.append("(")
                dfs(open_ + 1, close)
                path.pop()
            if close < open_:
                path.append(")")
                dfs(open_, close + 1)
                path.pop()

        dfs(0, 0)
        return res

时间 \(O(\frac{4^n}{\sqrt n})\)（Catalan 数个结果，每个长 \(2n\)），空间 \(O(n)\)（不计输出）。

延伸

• 判定一个串是否合法用计数或栈——见 20. 有效的括号；本题的 close < open 就是那个计数器不许变负。
• 最长的合法子串是另一个方向——32. 最长有效括号，用栈或 DP。
• 另一种构造：合法串一定能唯一写成 (A)B，A、B 也合法——按 A 的对数枚举，得到 Catalan 的递推式，可以做记忆化。

s = Solution()
assert sorted(s.generateParenthesis(3)) == sorted(["((()))", "(()())", "(())()", "()(())", "()()()"])
assert s.generateParenthesis(1) == ["()"]
assert len(s.generateParenthesis(8)) == 1430  # C_8