题目描述
思路解析
一句话答案：LeetCode 22 括号生成的标准解法是回溯加剪枝：搭串时只有两条落子规则——左括号没用完（open < n）就能放「(」，存在落单的左括号（close < open）才能放「)」，凑满 2n 个字符即收进答案。时间约 O(4ⁿ/√n)，即第 n 个卡塔兰数的量级，递归深度 O(n)。
括号生成这道题到底在问什么
给定 n 对括号，要求列出所有「有效」的括号组合。有效的含义是：每个右括号往前看，都能找到一个还没被配对的左括号。注意题目要的是全部方案本身而不是方案个数，所以这是一道枚举型问题——必须把每一个合法串真正构造出来，计数公式帮不上忙。
为什么不先生成所有串再过滤
最直觉的暴力是：把长度 2n 的串每一位都在「(」和「)」里二选一，生成全部 2 的 2n 次方个候选，再逐个检查合法性。n = 3 时就是 64 个候选里挑 5 个，浪费惊人，n 一大更是指数级白干。
关键观察是：一个前缀能不能长成合法串，其实当场就能判定，只取决于两个计数——已放的左括号数 open 和右括号数 close。只要 close 超过 open，或者 open 超过 n，后面无论怎么补都救不回来。既然非法在半路就能看出来，就没必要等整串搭完再验，这正是回溯剪枝的用武之地：边搭边判，非法分支根本不进。
两条落子规则为什么恰好充分又必要
回溯的每一步只问两件事：open < n 吗？是就可以再放一个「(」，因为左括号配额还没用完。close < open 吗？是就可以放一个「)」，因为前面还有落单的左括号等着被配对；若 close 已经追平 open，再放右括号就没有搭档，必然非法。
这两条规则保证了不重不漏。不漏：任何一个合法串，它的每个前缀都天然满足「右括号数不超过左括号数、左括号数不超过 n」，所以这条路径在决策树里一定走得通。不重：每一步先试「(」再试「)」，每个串对应树上唯一一条路径。于是当 len(path) == 2n 时，open 和 close 必然都等于 n，收进结果的一定是完整合法串，连最终校验都省了。
剪枝到底省掉了多少工作量
不剪枝的搜索空间是 2 的 2n 次方，剪枝后真正被展开的路径只有合法串本身加上少量当场夭折的分支。合法串的个数是第 n 个卡塔兰数 C(n) = (2n)! / ((n+1)! n!)，n = 3 时是 5 个：((()))、(()())、(())()、()(())、()()()。每个串长 2n，所以总时间约 O(4ⁿ/√n)——仍是指数，但这是输出规模决定的下限，算法本身没有一点冗余。
复杂度怎么算，哪些写法会翻车
时间约 O(4ⁿ/√n)，由卡塔兰数乘每串长度 2n 得出；空间 O(n)，只有深度 2n 的递归栈和一条 path。最常见的翻车点是把放右括号的条件写成 close < n：这样会放出没有搭档的右括号，产出 )( 这类非法串。另一个细节是收集完必须 return，否则 path 已满还继续往下试，会越界或重复收集。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这两条「能不能放」的判断，下面每一步都在套它。
从空 path 开始。最左一定先放「(」（空串放「)」必非法）。
左括号 0<3，没用完 → 放「(」。现在 path=「(」，左1右0。
左括号 1<3，没用完 → 放「(」。现在 path=「((」，左2右0。
左括号 2<3，没用完 → 放「(」。现在 path=「(((」，左3右0。
左括号已放满 3=3 → 不能再放「(」，剪掉这条分支 ✗。当前 path=「(((」，左3右0。
右括号 0<左括号 3 → 可以放「)」配对。现在 path=「((()」，左3右1。
左括号已放满 3=3 → 不能再放「(」，剪掉这条分支 ✗。当前 path=「((()」，左3右1。
右括号 1<左括号 3 → 可以放「)」配对。现在 path=「((())」，左3右2。
左括号已放满 3=3 → 不能再放「(」，剪掉这条分支 ✗。当前 path=「((())」，左3右2。
右括号 2<左括号 3 → 可以放「)」配对。现在 path=「((()))」，左3右3。
path 凑满 6 个字符 → 合法串「((()))」收进 results（第 1 个）。✅
右括号 0<左括号 2 → 可以放「)」配对。现在 path=「(()」，左2右1。
左括号 2<3，没用完 → 放「(」。现在 path=「(()(」，左3右1。
左括号已放满 3=3 → 不能再放「(」，剪掉这条分支 ✗。当前 path=「(()(」，左3右1。
右括号 1<左括号 3 → 可以放「)」配对。现在 path=「(()()」，左3右2。
左括号已放满 3=3 → 不能再放「(」，剪掉这条分支 ✗。当前 path=「(()()」，左3右2。
右括号 2<左括号 3 → 可以放「)」配对。现在 path=「(()())」，左3右3。
path 凑满 6 个字符 → 合法串「(()())」收进 results（第 2 个）。✅
右括号 1<左括号 2 → 可以放「)」配对。现在 path=「(())」，左2右2。
左括号 2<3，没用完 → 放「(」。现在 path=「(())(」，左3右2。
左括号已放满 3=3 → 不能再放「(」，剪掉这条分支 ✗。当前 path=「(())(」，左3右2。
右括号 2<左括号 3 → 可以放「)」配对。现在 path=「(())()」，左3右3。
path 凑满 6 个字符 → 合法串「(())()」收进 results（第 3 个）。✅
右括号 2=左括号 2，没有落单的「(」可配 → 放「)」非法，剪掉 ✗。当前 path=「(())」，左2右2。
右括号 0<左括号 1 → 可以放「)」配对。现在 path=「()」，左1右1。
左括号 1<3，没用完 → 放「(」。现在 path=「()(」，左2右1。
左括号 2<3，没用完 → 放「(」。现在 path=「()((」，左3右1。
左括号已放满 3=3 → 不能再放「(」，剪掉这条分支 ✗。当前 path=「()((」，左3右1。
右括号 1<左括号 3 → 可以放「)」配对。现在 path=「()(()」，左3右2。
左括号已放满 3=3 → 不能再放「(」，剪掉这条分支 ✗。当前 path=「()(()」，左3右2。
右括号 2<左括号 3 → 可以放「)」配对。现在 path=「()(())」，左3右3。
path 凑满 6 个字符 → 合法串「()(())」收进 results（第 4 个）。✅
右括号 1<左括号 2 → 可以放「)」配对。现在 path=「()()」，左2右2。
左括号 2<3，没用完 → 放「(」。现在 path=「()()(」，左3右2。
左括号已放满 3=3 → 不能再放「(」，剪掉这条分支 ✗。当前 path=「()()(」，左3右2。
右括号 2<左括号 3 → 可以放「)」配对。现在 path=「()()()」，左3右3。
path 凑满 6 个字符 → 合法串「()()()」收进 results（第 5 个）。✅
右括号 2=左括号 2，没有落单的「(」可配 → 放「)」非法，剪掉 ✗。当前 path=「()()」，左2右2。
右括号 1=左括号 1，没有落单的「(」可配 → 放「)」非法，剪掉 ✗。当前 path=「()」，左1右1。
右括号 0=左括号 0，没有落单的「(」可配 → 放「)」非法，剪掉 ✗。当前 path=「」，左0右0。
回溯走完整棵决策树，共收集到 5 个合法串：((()))、(()())、(())()、()(())、()()()。
边界先想清，n=0 返回含空串的列表。
两个高频追问。
参考代码
def generateParenthesis(n): res = [] def bt(path, open, close): if len(path) == 2 * n: res.append("".join(path)); return if open < n: bt(path + ["("], open + 1, close) if close < open: bt(path + [")"], open, close + 1) bt([], 0, 0) return res复杂度
- 时间：~O(4ⁿ/√n)，结果个数是第 n 个卡塔兰数，每个串长 2n
- 空间：O(n)，递归深度 2n + path
易错点
面试追问把动画讲成自己的话
追问为什么结果数是卡塔兰数？
追问能不能不用递归？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
每日温度
LeetCode 739 · 中等 · 沿着 栈 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题