22. 括号生成

数字 $n$ 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：

python">输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

python">输入：n = 1
输出：["()"]

算法思路

该代码采用 回溯法 生成所有有效的括号组合。通过递归逐步构建可能的括号字符串，并利用剪枝条件（左括号数量不超过 $n$，右括号数量不超过左括号数量）确保每一步生成的字符串均有效。核心思路如下：

步骤详解

1. 初始化参数：
   • ans存储所有有效组合。
   • backtrack函数接收当前字符串 S、已用左括号数 left 和右括号数 right。
2. 递归终止条件：
   • 当 S 的长度等于 2n 时，将当前字符串加入 ans。
3. 递归生成括号：
   • 添加左括号： 若 left < n，添加左括号并递归处理 left + 1，回溯时删除该左括号。
   • 添加右括号： 若 right < left（保证右括号有效），添加右括号并递归处理 right + 1，回溯时删除该右括号。

关键点

1. 剪枝条件：
   • 左括号数不超过 n，保证总数不超限。
   • 右括号数不超过左括号数，避免无效组合，如 “)(”。
2. 回溯恢复状态：
   • 每次递归调用后移除刚添加的括号，确保后续分支正确遍历其他可能性。
3. 动态维护路径：
   • 通过列表 S 记录当前路径，避免字符串拼接带来的额外开销。

复杂度分析

• 时间复杂度：$O(4^n/\surd n)$
  • 有效组合数为卡特兰数 $C(n)=(1/(n+1))\ast C(2n,n)\approx O(4^n/n\surd n)$
  • 每个组合生成需 $O(n)$ 时间，总时间为 $O(n\ast C(n))=O(4^n/\surd n)$。
• 空间复杂度：
  • 递归栈空间： $O(n)$，递归深度为 $2n$。
  • 结果存储： $O(4^n/\surd n)$，存储所有有效组合（每个长度为 $2n$）。

算法代码

python">class Solution:def generateParenthesis(self, n: int) -> List[str]:ans = []def backtrack(S, left, right):if len(S) == 2 * n:ans.append(''.join(S))returnif left < n:S.append('(')backtrack(S, left+1, right)S.pop()if right < left:S.append(')')backtrack(S, left, right+1)S.pop()backtrack([], 0, 0)return ans

该问题与普通回溯问题的核心区别

括号生成问题虽然使用回溯框架，但其约束条件和解空间特性与普通回溯问题（如全排列、子集）有显著差异。以下是具体对比：

---

1. 剪枝条件的特殊性

维度	括号生成	普通回溯（如全排列）
剪枝目标	保证括号有效性（左括号数 ≥ 右括号数）	避免重复选择同一元素
剪枝条件	left < n 和 right < left	通过标记数组或交换法保证元素不重复
约束类型	动态约束：依赖当前路径的左右括号数量关系	静态约束：仅依赖已选元素是否重复

示例说明：

• 括号生成中，右括号的添加必须满足 right < left，否则会导致无效组合（如 ")("）。
• 全排列中，只需确保每个元素仅被使用一次。

---

2. 状态参数的动态管理

维度	括号生成	普通回溯（如全排列）
状态参数	需跟踪 left（左括号数）和 right（右括号数）	通常只需跟踪 当前路径长度 或 已选元素
状态更新	每次递归需更新 left 或 right	通常只需更新路径和标记数组
状态恢复	回溯时需恢复路径和计数器（代码中通过 S.pop()）	类似，需恢复路径和标记状态

示例说明：

• 括号生成中，递归参数 left 和 right 动态约束下一步的选择范围。
• 全排列中，通过交换元素位置或标记数组管理元素是否已被使用。

---

3. 解的结构与有效性

维度	括号生成	普通回溯（如全排列）
解的有效性	必须满足括号匹配规则（平衡且嵌套正确）	只需满足元素不重复
解空间特性	有效解的数量为卡特兰数（C(n) = O(4ⁿ/√n)）	全排列解的数量为阶乘（n!）
生成方式	通过左右括号的合法组合生成	通过元素的排列组合生成

示例说明：

• 括号生成的有效解必须成对出现，如 "(()())"。
• 全排列的有效解只需包含所有元素一次，如 [1,2,3] 的排列。

---

4. 选择列表的动态性

维度	括号生成	普通回溯（如全排列）
选择列表	根据 left 和 right 动态决定可选括号类型	根据未使用的元素静态确定选择列表
选择策略	优先添加左括号，再在条件允许时添加右括号	遍历所有未选元素

示例说明：

• 当 left < n 时，可选择添加左括号；当 right < left 时，可选择添加右括号。
• 全排列中，每一步选择列表为所有未被使用的元素。

---

总结对比表

对比维度	括号生成	普通回溯问题（如全排列）
核心约束	动态括号匹配规则（左 ≥ 右，总数 ≤ n）	静态元素唯一性
剪枝条件	基于左右括号数量的实时关系	基于元素是否已被使用
解空间大小	卡特兰数（指数级但比全排列少）	阶乘级（更大）
状态管理复杂度	需额外维护左右括号计数器	通常仅需管理路径和标记数组
时间复杂度	O(4ⁿ/√n)	O(n × n!)

---

关键区别总结

1. 剪枝逻辑的实时性：括号生成的剪枝条件依赖当前路径的实时状态（左右括号数），而普通回溯通常依赖静态的未使用元素集合。
2. 解的有效性规则：括号生成需满足严格的括号平衡规则，普通回溯只需满足元素不重复。
3. 解空间的数学特性：括号生成的解空间由卡特兰数描述，远小于全排列的阶乘级解空间。
4. 状态参数的复杂性：括号生成需维护左右括号数量，增加了状态管理的维度。