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

LeetCode【0022】括号生成

article 2024/11/14 6:09:24

本文目录

1 中文题目
2 求解方法：回溯法
- 2.1 方法思路
- 2.2 Python代码
- 2.3 复杂度分析
3 题目总结

1 中文题目

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

示例：

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

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

提示：

$\leq n \leq 8$

2 求解方法：回溯法

2.1 方法思路

方法核心

使用回溯法生成所有可能的括号组合，回溯算法的约束条件：
- 任意时刻，已使用的右括号数量不能超过已使用的左括号数量
- 左括号和右括号的总数量都不能超过n
- 当左右括号都用完时，得到一个有效组合
通过左右括号数量的关系确保生成的括号组合有效
使用剪枝策略避免生成无效的括号组合

实现步骤

初始化
- 创建空的结果列表，设置初始左右括号数量为n
- 调用回溯函数，从空字符串开始构建
- 递归过程中根据条件选择添加左括号或右括号
- 当左右括号都用完时，将当前字符串加入结果列表
括号添加规则
- 只要还有左括号，就可以添加左括号（left > 0）
- 只有当右括号剩余数量大于左括号时，才能添加右括号（right > left）
递归终止条件
- 当left和right都为0时，找到一个有效组合
- 将current加入result列表
- 返回上一层递归
有效性保证
- 任何时刻已使用的右括号数量不能超过已使用的左括号数量
- 通过right > left的判断条件来保证
- 左右括号的使用数量都不能超过初始值n
结果返回
- 回溯完成后，result列表包含所有有效组合
- 直接返回result列表作为最终结果

方法示例

输入：n = 2
过程演示：

# 初始状态：left=2, right=2, current=""
└── ""
    
# 第一层递归：可以添加左括号
└── "("  (left=1, right=2)
    
# 第二层递归：可以添加左括号或右括号
├── "((" (left=0, right=2)  # 添加左括号
└── "()" (left=1, right=1)  # 添加右括号
    
# 第三层递归：
├── "(()" (left=0, right=1)  # 从"(("添加右括号
└── "()(" (left=0, right=1)  # 从"()"添加左括号
    
# 第四层递归：
├── "(())" (left=0, right=0)  # 从"(()"添加右括号
└── "()()" (left=0, right=0)  # 从"()("添加右括号

最终结果：["(())", "()()"]

2.2 Python代码

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # 结果列表，存储所有有效的括号组合
        result = []
        
        def backtrack(left: int, right: int, current: str):
            """
            回溯函数
            left: 剩余可用的左括号数量
            right: 剩余可用的右括号数量
            current: 当前已生成的括号字符串
            """
            # 当左右括号都用完时，找到一个有效组合
            if left == 0 and right == 0:
                result.append(current)
                return
            
            # 只要还有剩余的左括号，就可以添加左括号
            if left > 0:
                backtrack(left - 1, right, current + "(")
            
            # 只有当剩余的右括号数量大于剩余的左括号数量时
            # 才可以添加右括号，这样确保括号组合有效
            if right > left:
                backtrack(left, right - 1, current + ")")
        
        # 初始调用回溯函数，开始时左右括号都有n个
        backtrack(n, n, "")
        return result