题目描述
给 n 对括号，生成所有合法的括号组合（每个左括号都能正确配对）。
思路解析
把所有 ( 和 ) 的排列都生成出来(n=3 就是 2^6=64 个)再挑合法的，绝大多数都是 "())( " 这种废串，白生成。
转折：把「合法」翻译成「什么时候能往下放」。构建过程中只要发现这一步会让前缀非法，立刻掐断这条分支，连试都不试，省掉所有废串。
两条规则：左括号还有剩(left 大于 0)就能放 (；已放的右括号比左括号少(right 大于 left 才有剩)，才能放 )。守住这两条，生成的一定合法。
放第 1 个：(：开局只能放 (（一个右括号都没法配对，放 ) 会立刻右多于左）。路径变成 "("，左括号还剩 2 个，右括号此刻不能放。
连放左括号到底：沿「优先放 (」这条分支一路放，把 3 个左括号都放完，路径 "((("。左括号用光(left=0)，接下来只能放右括号。
补齐右括号 · 收第 1 条：此时 right(3) 大于 left(0)，能连放 3 个右括号，得到 "((()))"。长度到 2n=6、左右配平 → 收进结果。这条分支到头，往回退。
回溯一步 · 试 close 剪枝：回退到只放了一个 ( 的地方，改走「先放 )」：path="()"，此时 open=1、close=1。若再放 )，会变成 close 大于 open(右多于左) → 负例分支，剪枝不展开，连递归都不进。
该分支只能放 ( · 续 "(()"：所以 "()" 后面只能放 (，得到 "(()"。左括号还剩 1、右括号还差 2，继续往下放就能凑出以 "()" 开头的几个解。
续放右括号 · 收 "()(())"：沿 "(()" 这条把剩下的 (、) 按规则补满，凑出 "()(())"，长度到 6 → 收下。中途收到的 "(()())"、"(())()" 也是这套放-收流程产出的。
回到底层 · 换最后一条：继续回溯，在 "()" 之后走「(后接)」这一路：path="()()"，open=close=2，再放 ( 放 ) 补满 → "()()()"。每一步都靠两条规则把住，不会拐进废串。
所有分支走完：这样不断「放-收-回退-换-该剪就剪」，把每条合法路径都走一遍，废分支一律掐死，最终凑齐全部 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)，靠剪枝只走合法分支
- 空间复杂度：O(n) —— 递归深度最多 2n，path 也最多 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（右括号必须比左括号「少」才能再放 )。写成 right>0 时，比如 path="(" 也会去放 )，凑出 "()" 没问题，但 path=")" 这种会冒出来，导致 )( 这种配不上对的串）
- 错误写法：收结果时直接存 path 引用 → 正确写法：存 "".join(path) 或 path[:] 的快照（path 后面还会被 pop/修改，存引用会让结果列表里的每一项都变成最后那条）
- 错误写法：用 path + ["("] 之外还手动回溯 → 正确写法：二选一：要么传新列表、要么 append 后 pop（混用会重复撤销，路径乱套）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。