22. Generate Parentheses

解题思路：

题目要求生成 n 对有效的括号组合。可以使用 回溯法 (Backtracking) 进行递归搜索。

思路解析：

1. 定义状态：

   • 需要生成 n 对括号，每个组合的长度为 2 * n。
   • 使用 left 记录当前已使用的左括号 ( 数量。
   • 使用 right 记录当前已使用的右括号 ) 数量。
   • 约束条件：right 不能超过 left，否则会形成无效括号。

2. 递归构造：

   • 若 left < n，可以添加 ( 继续递归。
   • 若 right < left，可以添加 ) 继续递归。
   • 若 left == n 且 right == n，说明找到一个完整的括号组合，加入结果列表。

3. 剪枝优化：

   • 若 left > n 或 right > left，直接返回，不进入递归。

---

代码实现：

from typing import List

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []

        def backtrack(current, left, right):
            # 终止条件：当左右括号都用完时，加入结果
            if left == n and right == n:
                result.append("".join(current))
                return

            # 选择 '('，如果左括号数量还没达到 n
            if left < n:
                current.append("(")
                backtrack(current, left + 1, right)
                current.pop()  # 回溯

            # 选择 ')'，必须保证右括号数量小于左括号
            if right < left:
                current.append(")")
                backtrack(current, left, right + 1)
                current.pop()  # 回溯

        # 递归入口
        backtrack([], 0, 0)
        return result

---

复杂度分析：

• 时间复杂度: $O(4^n / \sqrt{n})$
  • 这是卡特兰数 C_n = \frac{1}{n+1} \binom{2n}{n} 的渐近上界。
• 空间复杂度: $O(n)$（递归栈深度最大为 n）。

---

示例：

输入：

sol = Solution()
print(sol.generateParenthesis(3))

输出：

["((()))", "(()())", "(())()", "()(())", "()()()"]

解析：

对于 n=3，所有有效的括号组合如下：

((()))
(()())
(())()
()(())
()()()

本方法通过回溯逐步构建所有可能的组合，并通过约束条件剪枝无效路径，保证了高效性。