22. 括号生成 (Medium)
专题归类： 08-回溯算法 LeetCode 链接： https://leetcode.cn/problems/generate-parentheses/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
题目详细分析
数据范围含义：
n <= 8：总组合数为第 n 个卡特兰数 C_n = (2n)!/(n!(n+1)!)。n=8 时 C_8 = 1430，完全可枚举。
有效括号的定义：
- 左括号数 = 右括号数 = n。
- 在任意前缀中，左括号数 >= 右括号数（即不会出现右括号比左括号多的情况——因为那样一定有一个右括号没有匹配的左括号在前）。
核心约束：
- 不能生成无效的括号组合（如
")("或"(()"）。 - 每个位置只能放
(或)两种选择，但受约束限制。
小白版直白理解
就像你要用”左括号”和”右括号”搭积木，搭出 n 对完整的”小房子”。每座小房子必须是一层一层搭起来的，不能先封顶再搭墙。
举个例子：(()) 就像先搭外层墙 (...)，再在里面搭 ()。()() 就像搭两个独立的 () 并排。
规则很简单：任何时候你放右括号 )，必须保证前面已经有左括号 ( 等着它——也就是说，已经放进去的左括号不能比右括号少。
解题思路
思路一：回溯 + 约束剪枝（推荐）
核心思想： 维护已使用的左括号数 left 和右括号数 right。每一步有两种选择——放左括号或放右括号，但受以下约束：
- 只有在
left < n时才能放左括号。 - 只有在
right < left时才能放右括号（右括号不能多于左括号）。
决策树可视化（以 n=2 为例）：
""
/ \
"(" ✗ (不能以 ) 开头)
/ \
"((" "()"
| / \
"(()" "()(" "()"→right>=left, 不合法
| |
"(())" "()()"
def generateParenthesis(n):
res = []
def backtrack(left, right, path):
# 左右括号都用完了，得到一个有效组合
if left == n and right == n:
res.append(path)
return
# 剪枝：左括号数不能超过 n
if left < n:
backtrack(left + 1, right, path + '(')
# 剪枝：右括号数不能超过左括号数
if right < left:
backtrack(left, right + 1, path + ')')
backtrack(0, 0, '')
return res思路二：剩余括号法（等价写法）
核心思想： 与思路一本质相同，但用”剩余数量”而非”已使用数量”来思考，对某些人更直观。
def generateParenthesis(n):
res = []
def backtrack(left_rem, right_rem, path):
# 没有剩余括号了
if left_rem == 0 and right_rem == 0:
res.append(path)
return
# 还有左括号剩余，可以放左括号
if left_rem > 0:
backtrack(left_rem - 1, right_rem, path + '(')
# 剩余的右括号多于左括号时才能放右括号
if right_rem > left_rem:
backtrack(left_rem, right_rem - 1, path + ')')
backtrack(n, n, '')
return res时间复杂度： O(4^n / sqrt(n))，即第 n 个卡特兰数的复杂度。 空间复杂度： O(n)，递归栈深度为 2n。
易错点
- 右括号的约束条件写错：
right < left（已使用角度）或right_rem > left_rem（剩余角度）。如果写成right <= left，就会在right == left时允许放右括号，产生无效的())序列。 - 忘记字符串的不可变性：Python 中字符串是不可变的，
path + '('产生新字符串，无需显式撤销。如果使用列表path.append则需要path.pop撤销。 - 初始调用：
backtrack(0, 0, '')不能以右括号开始，约束自然阻止了这种情况。 - n 的边界：n=1 时正确输出
["()"]，n=0 时（虽然题目给出 n>=1）应返回[""]。
框架提炼
约束回溯的通用模板：
def backtrack(状态参数, 路径):
if 达到目标状态:
记录结果
return
for 选择 in ['(', ')']: # 或更多选择
if 不满足约束条件:
continue # 剪枝
做选择(更新状态)
backtrack(新状态, 新路径)
撤销选择有效括号的充要条件（可推广到类似问题）：
- 最终左右括号数相等。
- 任意前缀中，左括号数 >= 右括号数。
这个原则也适用于验证括号是否有效（20-有效的括号）、判断最长有效括号（32）等。
卡特兰数： 许多回溯问题（括号生成、不同的二叉搜索树、出栈序列等）的结果数都是卡特兰数 Cn = (2n)!/(n!(n+1)!)。
关联题目
- 46-全排列 — 标准回溯（无条件）vs 括号生成（有条件约束），对比学习的经典组合。
- 17-电话号码的字母组合 — 另一类多叉树回溯，每层选择列表由输入决定。
- 20-有效的括号 — 括号验证问题，使用的合法性判断条件与本题完全一致。
- 95-不同的二叉搜索树II — 同样是卡特兰数结构的枚举问题，思路可以互相借鉴。