22. 括号生成

题目链接（中等）

题目描述

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

数据范围：1 <= n <= 8

示例

示例 1：

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

示例 2：

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

方法一：暴力法

思路及解法

生成所有 $2^{2n}$ 个括号序列（每步加 ( 或 )），再逐个检查有效性。

有效性检查：用 balance 记录左括号数减右括号数：

遍历中若 balance < 0，说明右括号多于左括号，无效；
遍历结束时 balance != 0，说明左右括号数量不等，无效。

代码

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)$，共 $2^{2n}$ 个序列，每个序列的生成与验证为 $O(n)$。
空间复杂度：$O(n)$，递归栈最多 $2n$ 层。

方法二：回溯

思路及解法

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

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

这样生成的每个序列都是有效的，无需额外验证。

代码

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)$，递归栈深度最多 $2n$。

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

思路及解法

任何合法序列都可写成 (a)b，其中 a、b 都是合法括号序列（可为空）。

枚举第一个 ( 对应的 ) 位置，即 a 包含 c 对括号（0 <= c < n），则：

a = generateParenthesis(c)；
b = generateParenthesis(n - 1 - c)；
拼接为 '(' + a + ')' + b。

用 @lru_cache 缓存每个 generateParenthesis(i) 的结果，避免重复递归。

代码

from functools import lru_cache

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

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

复杂度分析

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

三种方法对比

方法	时间	空间	特点
暴力法	$O(2^{2n} \cdot n)$	$O(n)$	思路最直接，但大量无效序列
回溯	$O(4^n/\sqrt{n})$	$O(n)$	剪枝后只生成有效序列，面试首选
按长度递归	$O(4^n/\sqrt{n})$	$O(4^n/\sqrt{n})$	数学分解清晰，但缓存占空间

总结

本质：生成所有合法括号序列，数量为卡特兰数；
暴力法：枚举所有 $2^{2n}$ 个序列，再验证，效率低；
回溯法：
- 左括号 < n 时放 (；
- 右括号 < 左括号 时放 )；
- 只在有效时才继续，天然剪枝；
按长度递归：(a)b 分解，枚举 a 的长度，缓存子问题；
通用套路：「生成所有合法组合」→ 回溯 + 剪枝，利用约束条件提前排除无效分支。

22. 括号生成

22. 括号生成

题目描述

示例

方法一：暴力法

思路及解法

代码

复杂度分析

方法二：回溯

思路及解法

代码

复杂度分析

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

思路及解法

代码

复杂度分析

三种方法对比

总结

相关题目