22. 括号生成

题目

22. 括号生成（中等）

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

示例 1：

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

示例 2：

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

数据范围：1 ≤ n ≤ 8

思路

方法一：暴力法

生成所有 $2^{2n}$ 个括号序列（每步加 ( 或 )），再逐个检查有效性：用 balance 记录左括号数减右括号数，遍历中 balance < 0 或结束时 balance != 0 即无效。

方法二：回溯

只在序列仍然有效时才添加括号，通过跟踪已放置的左右括号数量剪枝：

• 左括号数量 < n 时，可以放 (
• 右括号数量 < 左括号数量 时，可以放 )

方法三：按括号序列的长度递归

任何合法序列都可写成 (a)b，其中 a、b 都是合法括号序列（可为空）。枚举第一个 ( 对应的 ) 位置 2i+1，递归求 a = generate(i) 与 b = generate(n-1-i)，拼接所有组合；用 @lru_cache 缓存每个 generate(i) 的结果，避免重复递归。

代码

方法一：暴力法

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def valid(s):
            bal = 0
            for c in s:
                if c == '(':
                    bal += 1
                else:
                    bal -= 1
                if bal < 0:
                    return False
            return bal == 0

        def fun(s):
            if len(s) == 2 * n:
                if valid(s):
                    ans.append(''.join(s))
            else:
                s.append('(')
                fun(s)
                s.pop()
                s.append(')')
                fun(s)
                s.pop()

        ans = []
        fun([])
        return ans

• 时间复杂度 $O(2^{2n} \cdot n)$（每个序列的生成与验证为 $O(n)$），空间复杂度 $O(n)$（递归栈最多 $2n$ 层）

方法二：回溯

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        def fun(s, left, right):
            if len(s) == 2 * n:
                ans.append(''.join(s))
                return
            if left < n:
                s.append('(')
                fun(s, left+1, right)
                s.pop()
            if right < left:
                s.append(')')
                fun(s, left, right + 1)
                s.pop()

        ans = []
        fun([], 0, 0)
        return ans

• 答案个数为第 $n$ 个卡特兰数 $\frac{1}{n+1}\binom{2n}{n}$，由 $O(4^n/\sqrt{n})$ 界定；时间复杂度 $O(4^n/\sqrt{n})$，空间复杂度 $O(n)$（递归栈）

方法三：按括号序列的长度递归

class Solution:
    @lru_cache(None)
    def generateParenthesis(self, n: int) -> list[str]:
        if n == 0:
            return ['']
        ans = []
        for c in range(n):
            for a in self.generateParenthesis(c):
                for b in self.generateParenthesis(n-1-c):
                    ans.append('({}){}'.format(a, b))
        return ans

• 时间复杂度 $O(4^n/\sqrt{n})$，空间复杂度 $O(4^n/\sqrt{n})$（除答案外还需存储同量级的中间结果）

@lru_cache(None)：functools 中的装饰器，缓存函数返回值，同一 n 重复调用时直接返回缓存；None 表示缓存无上限。用在实例方法上时 self 也会进入缓存键，通常无碍。