当前位置：首页 > article >正文

【LeetCode 热题100】 22. 括号生成的算法思路及python代码

article 2025/3/26 21:11:30

22. 括号生成

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

示例 1：

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

示例 2：

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

算法思路

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

步骤详解

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

关键点

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

复杂度分析

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

算法代码

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def backtrack(S, left, right):
            if len(S) == 2 * n:
                ans.append(''.join(S))
                return
            if 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!)