企业官网建设流程全解析

LeetCode 22. 括号生成 — Python3 实现
问题描述
给定 n 对括号，生成所有由 n 对括号组成的有效（格式正确）的括号组合。
输入: n = 3输出: [“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
解题思路：回溯法
核心规则：
• 任意时刻，左括号数 left ≥ 右括号数 right（保证合法性）
• 左括号总数 ≤ n
• 右括号总数 ≤ n
“” / \ “(” 无效(left<right) / \ “((” “()” / \ / “(((” “(()” “()(” “())” ← “())” 非法…
代码实现
方法一：回溯法（推荐 ✅）
【python】
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
self.backtrack(result, “”, 0, 0, n)
return result
def backtrack(self, result: List[str], current: str, left: int, right: int, n: int):
# 终止条件：左右括号都用完了
if len(current) == 2 * n:
result.append(current)
return
# 尝试添加左括号
if left < n:
self.backtrack(result, current + “(”, left + 1, right, n)
# 尝试添加右括号（必须 left > right 才合法）
if right < left:
self.backtrack(result, current + “)”, left, right + 1, n)
方法二：使用闭包（更 Pythonic）
【python】
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
def backtrack(current: str, left: int, right: int):
if len(current) == 2 * n:
result.append(current)
return
if left < n:
backtrack(current + “(”, left + 1, right)
if right < left:
backtrack(current + “)”, left, right + 1)
backtrack(“”, 0, 0)
return result
方法三：动态规划
【python】
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return [“”]
# dp[i] 表示 i 对括号的所有有效组合
dp = [[] for _ in range(n + 1)]
dp[0] = [“”]
for i in range(1, n + 1):
# 将 i 对括号分解为：内部 j 对 + 外部 (1对)
for j in range(i):
for left in dp[j]:
for right in dp[i - 1 - j]:
dp[i].append(“(” + left + “)” + right)
return dp[n]
DP 思路图解（n=3）：
dp[3] = “(” + dp[0] + “)” + dp[2] → “()” + dp[2] + “(” + dp[1] + “)” + dp[1] → “(())” + dp[1] + “(” + dp[2] + “)” + dp[0] → “((()))”
测试验证
【python】
ifname== “main”:
sol = Solution()
print(sol.generateParenthesis(1))
# [‘()’]
print(sol.generateParenthesis(2))
# [‘(())’, ‘()()’]
print(sol.generateParenthesis(3))
# [‘((()))’, ‘(()())’, ‘(())()’, ‘()(())’, ‘()()()’]
复杂度分析
【表格】
指标 值
时间复杂度 O(4ⁿ/√n)，即第 n 个卡特兰数
空间复杂度 O(4ⁿ/√n)（结果存储）+ O(n)（递归栈深）
卡特兰数公式：Cₙ = (1/(n+1)) × C(2n, n)
方法对比
【表格】
方法 优点 缺点
回溯法 直观易理解，效率高 递归深度为 2n
动态规划 无递归，适合学习 DP 思想 理解稍复杂，中间状态多
关键点总结

1. 剪枝条件：right < left → 才能放右括号2. 终止条件：len(current) == 2 * n3. 字符串拼接：Python 中直接用 + 拼接，每次产生新字符串4. 本质是生成第 n 个卡特兰数对应的所有合法括号序列