22. 括号生成

题目描述

给 n 对括号，生成所有合法的括号组合（每个左括号都能正确配对）。

思路解析

把所有 ( 和 ) 的排列都生成出来再挑合法的，绝大多数都是废串，白生成。

回溯的精髓——构建过程中只要发现不可能合法，立刻掐断这条分支，连试都不试。

两条规则：左括号还有剩就能放 (；已放的右括号比左括号少，才能放 )。守住这两条，生成的一定合法。

放第 1 个：(：开局只能放 (（一个 ) 都没法配对）。路径变成 "("，左括号还剩 2 个。

连放左括号：一路把 3 个左括号都放完，路径 "((("。左括号用光了，接下来只能放右括号。

补齐右括号：把 3 个右括号补上，得到 "((()))"。左右配平、长度够了，收进结果。

回溯，换分支：收完一条就往回退（撤销刚放的括号），回到还能拐弯的地方，改放 ) 试另一种走法。

所有分支走完：这样不断「放-收-回退-换」，把每条合法路径都走一遍，最终凑齐全部 5 种。

回溯类题的通用思路：把「什么时候合法」翻译成「什么时候能往下放」，不合法的分支直接不进，效率天差地别。

参考代码（Python）

1def generateParenthesis(n):
2    res = []
3    def bt(path, left, right):        # left/right = 还能放几个
4        if len(path) == 2 * n:
5            res.append(class="cl-str">"".join(path)); return
6        if left > 0:                  # 左括号有剩，能放 (
7            bt(path + [class="cl-str">"("], left - 1, right)
8        if right > left:              # 右比左多得剩，能放 )
9            bt(path + [class="cl-str">")"], left, right - 1)
10    bt([], n, n)
11    return res

复杂度分析

• 时间复杂度：第 n 个卡特兰数 —— 约 4ⁿ / (n√n)
• 空间复杂度：O(n) —— 递归深度 2n

套路模板

所有回溯都是这个骨架：到终点就收、否则枚举合法选择、选了再撤。本题用「left/right 计数」充当那个「状态」。

1def bt(path, 状态):
2    if 到达终点:
3        res.append(path 的快照); return
4    for 每个合法选择:
5        做选择（更新 path 和状态）
6        bt(path, 新状态)
7        撤销选择（回溯）

易错点

• ❌ 放 ) 的条件写成 right > 0 → ✅ right > left（右括号必须比左括号「少」才能再放 )，否则会出现 )( 这种配不上对的串）
• ❌ 收结果时直接存 path 引用 → ✅ 存 "".join(path) 或 path[:] 的快照（path 后面还会被修改，存引用会让结果全变成最后那条）
• ❌ 用 path + ["("] 之外还手动回溯 → ✅ 二选一：要么传新列表、要么 append 后 pop（混用会重复撤销，路径乱套）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。