22. 括号生成
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
输入：n = 1
输出：["()"]
约束：
1 <= n <= 8
解题思路
第一步：理解问题本质
有效括号组合的两个核心约束：
- 左括号总数 = 右括号总数 = n
- 在字符串的任意前缀中，左括号数量必须 >= 右括号数量（否则出现多余的右括号，无法匹配）
这两个约束决定了：在构建过程中的任意时刻，
- 已用左括号数
left< n 时，才能继续放左括号 - 已用右括号数
right< 已用左括号数left时，才能放右括号（确保右括号不超过左括号）
当右括号数量达到 n 时，说明整个字符串已经填满（共 2n 个字符），且合法，加入答案。
第二步：暴力解法
思路： 生成所有长度为 2n 的括号字符串，然后逐一验证是否合法。
class Solution:
def generateParenthesis(self, n: int):
def is_valid(s):
count = 0
for c in s:
if c == '(':
count += 1
else:
count -= 1
if count < 0:
return False
return count == 0
ans = []
# 生成所有 2^(2n) 种组合
for bits in range(1 << (2 * n)):
s = ''
for i in range(2 * n):
s += '(' if (bits >> i) & 1 else ')'
if is_valid(s):
ans.append(s)
return ans
为什么不够好：
- 时间复杂度 O(2^(2n) * n)：枚举了所有 2^(2n) 种字符串，绝大多数都是非法的，严重浪费
- 对于 n=8，需要枚举 2^16 = 65536 种字符串，但合法的只有 1430 种（第 8 个卡特兰数）
第三步：优化思路
暴力法的问题在于：在构建过程中，即使已经发现当前路径不可能产生合法括号（比如右括号已经多于左括号），仍然继续枚举。
改进方向：边构建边剪枝。一旦发现当前状态违反约束，立刻停止，不再向下搜索。这正是回溯（DFS + 剪枝）的核心思想。
第四步：最优解法（回溯 DFS）
状态定义：
left：已放入的左括号数量right：已放入的右括号数量- 当前位置下标 =
left + right（已放字符总数）
剪枝条件（合法性约束）：
- 只有
left < n时，才可以放左括号 - 只有
right < left时，才可以放右括号
终止条件：
right == n，说明已放了 n 个右括号（同时也有 n 个左括号），字符串构建完毕，加入答案
用预分配数组而非字符串拼接： 字符串每次拼接会产生新对象，而 path = [''] * (2n) 预先分配好，每次直接修改对应位置，最后一次性 join，效率更高。
完整代码实现
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
path = [''] * (n * 2) # 预分配长度为 2n 的数组
def dfs(left: int, right: int) -> None:
# 终止：已放 n 个右括号，字符串构建完毕
if right == n:
ans.append(''.join(path))
return
# 放左括号：还有剩余配额
if left < n:
path[left + right] = '(' # 当前位置 = 已放字符总数
dfs(left + 1, right)
# 放右括号：右括号数量未超过左括号
if right < left:
path[left + right] = ')'
dfs(left, right + 1)
dfs(0, 0)
return ans
示例推演
以 n = 2 为例，展示完整的 DFS 搜索树（left 为已放左括号数，right 为已放右括号数）：
dfs(0, 0) path=["",""] 当前位置 0
├── 放 '(' → dfs(1, 0) path=["(",""] 当前位置 1
│ ├── 放 '(' → dfs(2, 0) path=["(","("] 当前位置 2
│ │ └── 放 ')'（right=0 < left=2）→ dfs(2, 1) path=["(","(","",")",...] 当前位置 3
│ │ └── 放 ')'（right=1 < left=2）→ dfs(2, 2) path=["(","(",")",")"] 当前位置 4
│ │ └── right==n==2，加入 "(())" ✓
│ └── 放 ')'（right=0 < left=1）→ dfs(1, 1) path=["(",")",...] 当前位置 2
│ └── 放 '('（left=1 < n=2）→ dfs(2, 1) path=["(","(",")",...) ... 当前位置 3
│ └── 放 ')'（right=1 < left=2）→ dfs(2, 2) path=["(",")",","(",")",...]
│ └── right==n==2，加入 "()()" ✓
最终答案：["(())", "()()"]，共 2 种，符合预期（卡特兰数 C_2 = 2）。
逐步追踪第一条路径 "(())" 的 path 数组变化：
| 步骤 | 操作 | left | right | 当前位置 left+right | path |
|---|---|---|---|---|---|
| 初始 | - | 0 | 0 | - | ['','','',''] |
| 1 | 放 ( | 1 | 0 | 0 | ['(','','',''] |
| 2 | 放 ( | 2 | 0 | 1 | ['(','(','',''] |
| 3 | 放 ) | 2 | 1 | 2 | ['(','(',')', ''] |
| 4 | 放 ) | 2 | 2 | 3 | ['(','(',')',')'] |
| 5 | right==2==n | - | - | - | 加入 "(())" |
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(2^(2n) · n) | O(n) | 枚举所有字符串再验证，大量无效枚举 |
| 回溯 DFS（最优） | O(C_n · n) | O(n) | C_n 为第 n 个卡特兰数，仅枚举合法路径 |
卡特兰数 C_n 的近似值为 O(4^n / n^(3/2))，远小于 2^(2n) = 4^n。回溯通过剪枝，只访问合法状态，效率大幅提升。
空间复杂度 O(n)：递归栈深度最大为 2n（每次放一个字符），path 数组长度为 2n。
易错点总结
- 终止条件用
right == n而非left == n： 必须等右括号也全部放完，字符串才是完整合法的。若只检查left == n，此时可能右括号还没放完。 - 当前位置下标是
left + right： 已放的字符总数恰好是left + right，这是预分配 path 数组的关键索引。 - 两个 if 是独立的，不是 if-else： 在同一状态下，放左括号和放右括号是两个独立的分支，都需要尝试（只要满足各自条件）。
- path 复用无需回溯清除： 由于
path[left + right] = ...总是写入确定的位置（由当前的 left 和 right 唯一确定），下一次写入会覆盖该位置，无需手动清除。
扩展思考
- 卡特兰数（Catalan Number）： n 对括号的合法组合数恰好是第 n 个卡特兰数 C_n = C(2n,n)/(n+1)。卡特兰数在算法中非常常见，如二叉搜索树的结构数、三角剖分方案数等。
- 动态规划解法：
dp[n]可以由dp[i]和dp[n-1-i]（i 从 0 到 n-1）组合得到，含义是第一对括号内有 i 对，括号外右侧有 n-1-i 对。 - 相关题目： LeetCode 20（有效的括号）用栈验证括号合法性，是本题合法性判断的逆问题；LeetCode 32（最长有效括号）在有效括号的基础上求最长子串。