题目描述
思路解析动画文字版
把所有 ( 和 ) 的排列都生成出来(n=3 就是 2^6=64 个)再挑合法的，绝大多数都是 "())( " 这种废串，白生成。
转折：把「合法」翻译成「什么时候能往下放」。构建过程中只要发现这一步会让前缀非法，立刻掐断这条分支，连试都不试，省掉所有废串。
两条规则（left/right = 已经放了几个左/右括号）：左括号没放满(left 小于 n)就能放 (；已放的右括号比左括号少(right 小于 left)才能放 )。守住这两条，生成的一定合法。
1. 开局只能放左括号：剪枝规则：left 没满(小于 n)才能放 (；right 比 left 少才能放 )。开局 left=right=0，放 ) 会先冒出右括号、非法 → 只能放 (。
2. 一路放左到 left=n：能放左就先放左，直到 left=3=n。此刻 left 已满，不能再放 (，只能开始补右括号。
3. 补满右括号 · 收第 1 条：左满后依次补 3 个 )，长度到 2n=6 → 第一条结果 ((())) 收集。
4. 关键帧 · 回溯换分支：回溯退回到前缀 ((，这次改放 )（right=0 比 left=2 少，允许放右）→ 新前缀 (()。剪枝条件决定了每一步能往哪走。
5. 沿新分支收第 2 条：从 (() 继续：放 ( 再补右 → 第二条 (()())。
6. 其余分支同理 · 收齐 5 条：继续回溯尝试其它合法前缀，依次得到 (())()、()(())、()()()。n=3 共 5 条（卡特兰数 C₃=5）。
回溯类题的通用思路：把「什么时候合法」翻译成「什么时候能往下放」，不合法的分支直接不进，效率天差地别。
迁移阶梯：把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
边界三连：边界三连：极端输入先过一遍。
几个高频追问，记住答法。
参考代码
class Solution: def generateParenthesis(self, n): ans = [] def backtrack(path, left, right): if len(path) == 2 * n: ans.append(''.join(path)) return if left < n: path.append('(') backtrack(path, left + 1, right) path.pop() if right < left: path.append(')') backtrack(path, left, right + 1) path.pop() backtrack([], 0, 0) return ans复杂度
- 时间复杂度：第 n 个卡特兰数，合法串约 4ⁿ/(n√n) 个，每个拼接花 O(n)，靠剪枝只走合法分支
- 空间复杂度：O(n)，递归深度最多 2n，path 也最多 2n 长
可套用的代码模板
所有回溯都是这个骨架：到终点就收、否则枚举合法选择、选了再撤。本题用「left/right 计数」充当那个「状态」，用计数条件做剪枝。
def bt(path, 状态): if 到达终点: res.append(path 的快照); return for 每个合法选择: 做选择（更新 path 和状态） bt(path, 新状态) 撤销选择（回溯）易错点
面试追问把动画讲成自己的话
追问为什么 close＜open 才能加右括号？
追问一共多少种结果？
追问和「生成所有 2^(2n) 再筛」有何不同？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
每日温度
LeetCode 739 · 中等 · 沿着 栈 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题