22. 括号生成

题目链接：22. 括号生成

题目描述

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

核心思考：带有约束的回溯法

生成所有组合的问题通常属于回溯（DFS）范畴。有效的括号组合必须满足两个核心硬性约束：

1. 左括号数量约束：左括号的总数不能超过 n。
2. 合法性约束：在生成过程中的任意时刻，已放置的右括号数量必须小于或等于左括号数量。如果右括号多于左括号，必然无法闭合形成合法序列。

基于此，我们可以设计如下回溯过程：

• 递归参数：记录当前已使用的左括号数 left 和右括号数 right。
• 填入左括号：如果 left < n，我们可以填入一个左括号，然后递归。
• 填入右括号：如果 right < left，说明当前存在未配对的左括号，我们可以填入一个右括号，然后递归。
• 终止条件：当 right == n 时，说明 n 对括号已全部配对完成，将当前路径字符串存入结果集。

这种方法只探索合法的路径，避免了生成无效括号对后再进行检查的大量无效计算。

解题思路 (Python)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        # 使用列表作为路径缓冲，总长度为 2n
        path = [""] * (n * 2)

        def dfs(left, right):
            # 所有右括号填充完毕，意味着组合合法且完成
            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

复杂度分析

• 时间复杂度：$O(\frac{4^n}{\sqrt{n}})$。这与卡特兰数（Catalan Number）相关，代表了第 $n$ 个卡特兰数所表示的合法序列总量。
• 空间复杂度：$O(n)$。由于结果不计入空间复杂度，这里的开销主要是递归栈深度以及路径数组 path。
  说明：代码中使用 path 列表而非字符串拼接，能有效减少在每一层递归中创建新字符串的内存开销。