LeetCode 22 Generate Parentheses 解题全解从暴力枚举到回溯剪枝的 O(4ⁿ/√n) 最优方案【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本篇文章基于本仓库 hints/generate-parentheses.md 提示文档系统讲解 LeetCode 22「括号生成」问题。仓库以 13 种语言实现了该题Python、Java、C、C、JavaScript、Go、Rust、Kotlin、Swift、C#、TypeScript、Ruby、Scala 等本文将先给出题目要求的复杂度基线再依次剖析暴力枚举、回溯剪枝与动态规划三种解法并结合 articles/generate-parentheses.md 与各语言源码佐证实现细节。读完你将掌握如何用open/close双计数器完成合法括号串的定向生成理解close open剪枝条件的本质并能独立写出时间 O(4ⁿ/√n)、空间 O(n) 的面试级最优解。一、题目与复杂度基线给定n对括号生成所有结构正确well-formed的括号组合。例如n 3时应返回((())) (()()) (())() ()(()) ()()()提示文档开篇明确给出了目标复杂度You should aim for a solution as good or better thanO(4ⁿ / √n) timeandO(n) space, wherenis the number of parenthesis pairs in the string.这一复杂度对应的是回溯剪枝与动态规划解法而暴力枚举的全量生成方案是 O(n · 2^(2n))两者差距巨大。n对括号的合法组合数量正是第 n 个卡特兰数C(n) (1 / (n 1)) · C(2n, n) ≈ 4ⁿ / (n^(3/2) · √π)这也是O(4ⁿ / √n)这个复杂度上界的由来——结果集本身的大小决定了任何解法至少需要这么多输出时间。二、暴力枚举生成全部再校验O(n · 2^(2n))2.1 思路如 hints/generate-parentheses.md 的 Hint 1 所述最直接的做法是A brute force solution would be to generate all possible strings of size2nand add only the valid strings. This would be anO(n * 2 ^ (2n))solution.即 DFS 枚举所有长度为2n的括号串每一位可选(或)共2^(2n)个逐个用括号平衡规则校验维护计数器balance已出现的开括号数遇到(加一遇到)减一一旦balance 0说明右括号过早出现字符串非法遍历结束后balance 0才合法所有开括号都被闭合。2.2 参考实现Pythonclass Solution: def generateParenthesis(self, n: int) - List[str]: res [] def valid(s: str): open 0 for c in s: open 1 if c ( else -1 if open 0: return False return not open def dfs(s: str): if n * 2 len(s): if valid(s): res.append(s) return dfs(s () dfs(s )) dfs() return res仓库中的 Kotlin 实现 kotlin/0022-generate-parentheses.kt 与暴力枚举思想一致先生成完整字符串再在末尾扫描校验close open时提前跳出、最终要求close open。2.3 复杂度时间复杂度O(2^(2n) · n)—— 生成2^(2n)个串每个串校验耗时 O(n)空间复杂度O(2^(2n) · n)—— 递归深度与结果暂存。问题在于大量无效串如)))(((被完整生成后才被丢弃浪费严重。这正是 Hint 1 中Can you think of a better way? Maybe you can use pruning所引导的改进方向。三、回溯剪枝只生成合法路径O(4ⁿ/√n)3.1 什么使字符串无效Hint 2 提出关键问题We can use backtracking with pruning. But what makes a string invalid? Can you think of a condition for this?Hint 3 给出了精确答案When the count of closing brackets exceeds the count of opening brackets, the string becomes invalid. Therefore, we can maintain two variables,openandclose, to track the number of opening and closing brackets. We avoid exploring paths whereclose open. Once the string length reaches2n, we add it to the result.也就是说在构建过程中的任意前缀一旦close open该分支即失效。例如前缀())中close 2 open 1后续无论追加什么都无法还原成合法串。3.2 算法骨架从空串出发维护两个计数器open已使用的(数量close已使用的)数量。每一步只做安全选择若open n可以追加(递归backtrack(open 1, close)若close open可以追加)递归backtrack(open, close 1)若open close n收集结果并返回。由于每一步都保证前缀合法到达2n长度时字符串必然整体合法无需再校验。3.3 参考实现Python与仓库提交版一致仓库提交版 python/0022-generate-parentheses.py 即采用此模板class Solution: def generateParenthesis(self, n: int) - List[str]: stack [] res [] def backtrack(openN, closedN): if openN closedN n: res.append(.join(stack)) return if openN n: stack.append(() backtrack(openN 1, closedN) stack.pop() if closedN openN: stack.append()) backtrack(openN, closedN 1) stack.pop() backtrack(0, 0) return res注意这里使用可变结构stack拼接字符串因此在递归返回后必须stack.pop()撤销选择——这正是回溯撤销上一步的核心动作。若改用不可变字符串拼接如s (则无需显式撤销如 Swift 版 swift/0022-generate-parentheses.swift 与 C 递归版 cpp/0022-generate-parentheses.cpp 所示void generate(int n, int open, int close, string str, vectorstring result) { if (open n close n) { result.push_back(str); return; } if (open n) { generate(n, open 1, close, str (, result); } if (open close) { generate(n, open, close 1, str ), result); } }3.4 剪枝条件在 C 语言中的直接体现C 语言版 c/0022-generate-parentheses.c 将剪枝表达得最直白——进入递归的第一步就检查closed open并直接返回void backtrack(char** results, int n, int open, int closed, Str* curr, int* returnSize) { if (closed open) { // This is the case when we prune the exploration of not well-formed parentheses return; } if (open closed 2 * n) { // create a copy of the qualifying buffer and save it in Results ... } ... }该实现同时展示了push_back/pop_back对缓冲区的手动管理pop_back时补写\0表示字符串结尾配合calloc的零初始化天然获得 C 字符串终止符。3.5 Rust 的计数递减变体Rust 版 rust/0022-generate-parentheses.rs 提供了另一种视角将open/close初始化为n每次添加字符即递减剩余额度终止条件变为open 0 close 0并用open close判断当前是否处于已平衡状态此时只能加(否则会造成close open的非法前缀fn backtrack(res: mut VecString, s: String, open: i32, close: i32) { if open 0 close 0 { res.push(s); return; } if open close { backtrack(res, s.clone() (, open - 1, close); } else { if open 0 { backtrack(res, s.clone() (, open - 1, close); } if close 0 { backtrack(res, s.clone() ), open, close - 1); } } }3.6 复杂度时间复杂度O(4ⁿ / √n)—— 只探索合法前缀节点总数与卡特兰数同阶空间复杂度O(n)—— 递归深度最多2n辅助stack长度为2n。四、动态规划由小规模答案组装大规模答案除了回溯articles/generate-parentheses.md 还给出了第三种思路每个合法括号串都可以表示成(left)right的形式——最外层一对括号包裹一个合法的left含i对其后紧跟一个合法的right含k - i - 1对。由此k对括号的所有结果都能由更小的子问题组合而来dp[k] ( dp[i] ) dp[k - i - 1]对全部 0 i k4.1 算法步骤dp[x]存放所有含x对括号的合法串边界dp[0] []空串本身合法对k 1..n枚举所有拆分点i按( dp[i] ) dp[k - i - 1]拼接返回dp[n]。4.2 参考实现Pythonclass Solution: def generateParenthesis(self, n): res [[] for _ in range(n 1)] res[0] [] for k in range(n 1): for i in range(k): for left in res[i]: for right in res[k - i - 1]: res[k].append(( left ) right) return res[-1]JavaScript 版 javascript/0022-generate-parentheses.js 同时收录了三种方案DFS 回溯、BFS 队列版本用[str, open, close]三元组作为队列元素终止条件为open n close n以及上述递归式 DP可作为对照学习材料。DP 方案的时间复杂度同样是 O(4ⁿ / √n)空间 O(n)若按层保留全部中间结果则为 O(4ⁿ / √n)。五、常见陷阱Common Pitfallsarticles/generate-parentheses.md 归纳了三个高频错误本仓库各语言实现刻意规避了它们值得重点记忆5.1 右括号添加条件写错close nvsclose open错误写法用close n作为添加)的条件会生成())(()这类右括号先于左括号闭合的非法串。正确条件close open。只有存在未匹配的左括号时才能追加右括号这正是 Hint 3 中close open即非法的直接推论。5.2 使用可变构建器时忘记回溯撤销使用List/StringBuilder/string等可变结构累积字符串时递归返回后必须移除刚追加的最后一个字符pop/deleteCharAt/pop_back。否则后续分支会残留上一次尝试的字符产生串扰。仓库中 Go 版 go/0022-generate-parentheses.go 为此专门封装了pop辅助函数func pop(list *[]string) { // since pop() function in go doesnt exist length : len(*list) *list (*list)[:length-1] }不可变字符串拼接每次递归创建新串虽免去显式撤销但会因反复创建中间字符串而消耗更多内存。5.3 终止条件理解偏差终止条件应显式写为open n close n而非仅判断length 2n。虽然对合法路径二者数学等价但显式双计数校验逻辑更清晰能帮助及早暴露分支条件错误导致的非法串漏网。六、仓库中的多语言实现索引本仓库为本题提供了完整的跨语言实现便于对照学习回溯模板在不同语言下的写法差异语言文件实现要点Pythonpython/0022-generate-parentheses.py回溯 显式 pop 撤销Ccpp/0022-generate-parentheses.cpp递归版与显式栈迭代版双实现Cc/0022-generate-parentheses.cclosed open剪枝 手动缓冲区管理JavaScriptjavascript/0022-generate-parentheses.jsDFS 回溯、BFS 队列、递归 DP 三方案Gogo/0022-generate-parentheses.go回溯 自封装 popRustrust/0022-generate-parentheses.rs剩余额度递减式回溯Kotlinkotlin/0022-generate-parentheses.kt全量生成 末尾校验Swiftswift/0022-generate-parentheses.swift不可变字符串拼接回溯七、小结以 hints/generate-parentheses.md 的三条提示为线索本题的解题路径清晰可循暴力枚举O(n · 2^(2n))→ 回溯剪枝O(4ⁿ / √n)、O(n)→ 动态规划组合。核心要点是用open/close双计数器保证任意前缀合法open n时才加(close open时才加)二者同时等于n时收集答案。这套边构建边剪枝的模式是面试中处理括号类、组合类问题的通用武器配合仓库内 8 语言的对照实现足以将本题吃透。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考