文心 LeetCode 22. 括号生成 Python3实现

LeetCode 22. 括号生成 — Python3 实现问题描述给定 n 对括号生成所有由 n 对括号组成的有效格式正确的括号组合。输入: n 3输出: [“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]解题思路回溯法核心规则• 任意时刻左括号数 left ≥ 右括号数 right保证合法性• 左括号总数 ≤ n• 右括号总数 ≤ n“” / \ “(” 无效(leftright) / \ “((” “()” / \ / “(((” “(()” “()(” “())” ← “())” 非法…代码实现方法一回溯法推荐 ✅【python】from typing import Listclass Solution:def generateParenthesis(self, n: int) - List[str]:result []self.backtrack(result, “”, 0, 0, n)return resultdef 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)returnif 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 思路图解n3dp[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/(n1)) × C(2n, n)方法对比【表格】方法 优点 缺点回溯法 直观易理解效率高 递归深度为 2n动态规划 无递归适合学习 DP 思想 理解稍复杂中间状态多关键点总结剪枝条件right left → 才能放右括号2. 终止条件len(current) 2 * n3. 字符串拼接Python 中直接用 拼接每次产生新字符串4. 本质是生成第 n 个卡特兰数对应的所有合法括号序列