LeetCode 22 括号生成Generate Parentheses全解暴力枚举、回溯剪枝与动态规划的多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以仓库 articles/generate-parentheses.md 为核心完整讲解 LeetCode 22「括号生成」的三种解法——暴力枚举、回溯Backtracking与动态规划并对照本仓库python/、cpp/、java/、javascript/、go/、rust/、ruby/等目录下的 0022-generate-parentheses.* 实现逐一验证。读完本文你将掌握如何从「生成全部再校验」逐步演进到「只构造合法括号串」的剪枝回溯写法并能用同一套思路解决其他「生成合法组合」类问题。问题定义给定n对括号生成所有**格式正确well-formed**的括号组合。例如n 3时结果为[((())), (()()), (())(), ()(()), ()()()]n 1时结果为[()]。仓库中的 C 实现cpp/0022-generate-parentheses.cpp在文件头注释里给出了这两个示例可作为自测用例。仓库 hints/generate-parentheses.md 给出了官方推荐的性能目标时间 $O(4^n / \sqrt{n})$、空间 $O(n)$其中n是括号对数。这意味着暴力解法只能作为理解问题的起点真正要追求的是回溯与动态规划解法。前置知识Prerequisites原文档明确列出了解这道题前需要熟悉的四块基础能力这也是本仓库其他题解反复使用的核心工具递归Recursion通过递归函数调用逐步构建解回溯Backtracking探索候选路径当路径导致无效状态时撤销选择动态规划Dynamic Programming由更小的子问题组合出更大的解字符串操作String Manipulation逐字符构建与校验字符串。如果你对回溯还比较陌生可以在本仓库中先阅读 combination-target-sum.md组合求和、permutations.md全排列等文章它们使用了完全相同的「递归 撤销选择」框架。解法一暴力枚举Brute Force核心直觉暴力法的思路最直接生成所有长度为2n、仅由(和)组成的字符串其中绝大多数是无效的因此对每个完整字符串做一次合法性校验维护一个计数器balance已出现的左括号数遇到(则balance 1遇到)则balance - 1若中途balance变成负数说明在某个位置右括号过多字符串无效遍历结束时balance必须为0说明所有左括号都被闭合。算法步骤使用 DFS 逐字符构建字符串s若len(s) 2n用上述 balance 规则校验s有效则加入结果集否则分两个分支继续尝试追加(尝试追加)返回收集到的所有结果。多语言实现原文档给出了 9 种语言的完整实现Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rustclass 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 respublic class Solution { public boolean valid(String s) { int open 0; for (char c : s.toCharArray()) { open c ( ? 1 : -1; if (open 0) return false; } return open 0; } void dfs(String s, ListString res, int n) { if (n * 2 s.length()) { if (valid(s)) res.add(s); return; } dfs(s (, res, n); dfs(s ), res, n); } public ListString generateParenthesis(int n) { ListString res new ArrayList(); dfs(, res, n); return res; } }class Solution { public: bool valid(const string s) { int open 0; for (char c : s) { open (c () ? 1 : -1; if (open 0) return false; } return open 0; } void dfs(string s, vectorstring res, int n) { if (s.length() 2 * n) { if (valid(s)) res.push_back(s); return; } dfs(s (, res, n); dfs(s ), res, n); } vectorstring generateParenthesis(int n) { vectorstring res; dfs(, res, n); return res; } };class Solution { /** * param {string} s * return {boolean} */ valid(s) { let open 0; for (const c of s) { open c ( ? 1 : -1; if (open 0) return false; } return open 0; } /** * param {string} s * param {string[]} * param {number} n */ dfs(s, res, n) { if (s.length 2 * n) { if (this.valid(s)) res.push(s); return; } this.dfs(s (, res, n); this.dfs(s ), res, n); } /** * param {number} n * return {string[]} */ generateParenthesis(n) { const res []; this.dfs(, res, n); return res; } }public class Solution { public bool Valid(string s) { int open 0; foreach (char c in s) { open (c () ? 1 : -1; if (open 0) return false; } return open 0; } public void Dfs(string s, Liststring res, int n) { if (s.Length 2 * n) { if (Valid(s)) res.Add(s); return; } Dfs(s (, res, n); Dfs(s ), res, n); } public Liststring GenerateParenthesis(int n) { Liststring res new Liststring(); Dfs(, res, n); return res; } }func generateParenthesis(n int) []string { res : make([]string, 0) var valid func(string) bool valid func(s string) bool { open : 0 for _, c : range s { if c ( { open } else { open-- } if open 0 { return false } } return open 0 } var dfs func(string) dfs func(s string) { if len(s) n*2 { if valid(s) { res append(res, s) } return } dfs(s () dfs(s )) } dfs() return res }class Solution { fun generateParenthesis(n: Int): ListString { val res mutableListOfString() fun valid(s: String): Boolean { var open 0 for (c in s) { if (c () open else open-- if (open 0) return false } return open 0 } fun dfs(s: String) { if (s.length n * 2) { if (valid(s)) { res.add(s) } return } dfs(s () dfs(s )) } dfs() return res } }class Solution { func generateParenthesis(_ n: Int) - [String] { var res [String]() func isValid(_ s: String) - Bool { var open 0 for c in s { open (c () ? 1 : -1 if open 0 { return false } } return open 0 } func dfs(_ s: String) { if s.count n * 2 { if isValid(s) { res.append(s) } return } dfs(s () dfs(s )) } dfs() return res } }impl Solution { pub fn generate_parenthesis(n: i32) - VecString { let mut res vec![]; fn valid(s: str) - bool { let mut open 0i32; for c in s.chars() { open if c ( { 1 } else { -1 }; if open 0 { return false; } } open 0 } fn dfs(s: String, n: i32, res: mut VecString) { if s.len() (n * 2) as usize { if valid(s) { res.push(s); } return; } dfs(s.clone() (, n, res); dfs(s ), n, res); } dfs(String::new(), n, mut res); res } }复杂度分析时间复杂度$O(2^{2n} \times n)$。共生成 $2^{2n}$ 个字符串每个字符串校验一次需要 $O(n)$ 遍历空间复杂度$O(2^{2n} \times n)$。需要保存所有字符串及其递归调用栈。当n 3时需要生成 $2^6 64$ 个字符串却只保留 5 个有效结果浪费极其严重。这正是 hints/generate-parentheses.md 中 Hint 1 所指出的优化空间用剪枝pruning避免生成无效字符串。解法二回溯Backtracking核心直觉与其生成所有字符串再校验合法性不如只构建合法字符串。合法括号串在任何前缀中都必须满足「右括号数不超过左括号数」因此每一步只做「安全选择」即可提前避开无效路径。回溯的三个关键规则只有在还有剩余左括号可用时open n才能添加(只有在不会破坏合法性的前提下close open才能添加)当open close n时字符串完整且合法加入结果。这对应 hints/generate-parentheses.md 中 Hint 3 的结论当右括号数量超过左括号数量时字符串变为无效因此维护open与close两个计数器并避免探索close open的路径。算法步骤从空字符串开始维护两个计数器open——已使用的(数量close——已使用的)数量若open close n将构建好的字符串加入结果若open n追加(并递归若close open追加)并递归每次选择后回溯撤销上一步的字符。多语言实现原文档给出的回溯版 9 语言实现注意 Python / Java / C / Go / Kotlin / Swift / Rust 使用可变构建器 显式撤销而 JavaScript / C# 直接使用不可变字符串拼接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 respublic class Solution { private void backtrack(int openN, int closedN, int n, ListString res, StringBuilder stack) { if (openN closedN openN n) { res.add(stack.toString()); return; } if (openN n) { stack.append((); backtrack(openN 1, closedN, n, res, stack); stack.deleteCharAt(stack.length() - 1); } if (closedN openN) { stack.append()); backtrack(openN, closedN 1, n, res, stack); stack.deleteCharAt(stack.length() - 1); } } public ListString generateParenthesis(int n) { ListString res new ArrayList(); StringBuilder stack new StringBuilder(); backtrack(0, 0, n, res, stack); return res; } }class Solution { public: void backtrack(int openN, int closedN, int n, vectorstring res, string stack) { if (openN closedN openN n) { res.push_back(stack); return; } if (openN n) { stack (; backtrack(openN 1, closedN, n, res, stack); stack.pop_back(); } if (closedN openN) { stack ); backtrack(openN, closedN 1, n, res, stack); stack.pop_back(); } } vectorstring generateParenthesis(int n) { vectorstring res; string stack; backtrack(0, 0, n, res, stack); return res; } };class Solution { /** * param {number} openN * param {number} closeN * param {number} n * param {string[]} res * param {string} stack */ backtrack(openN, closedN, n, res, stack) { if (openN closedN openN n) { res.push(stack); return; } if (openN n) { this.backtrack(openN 1, closedN, n, res, stack (); } if (closedN openN) { this.backtrack(openN, closedN 1, n, res, stack )); } } /** * param {number} n * return {string[]} */ generateParenthesis(n) { const res []; this.backtrack(0, 0, n, res, ); return res; } }public class Solution { public void Backtrack(int openN, int closedN, int n, Liststring res, string stack) { if (openN closedN openN n) { res.Add(stack); return; } if (openN n) { Backtrack(openN 1, closedN, n, res, stack (); } if (closedN openN) { Backtrack(openN, closedN 1, n, res, stack )); } } public Liststring GenerateParenthesis(int n) { Liststring res new Liststring(); string stack ; Backtrack(0, 0, n, res, stack); return res; } }func generateParenthesis(n int) []string { stack : make([]string, 0) res : make([]string, 0) var backtrack func(int, int) backtrack func(openN, closedN int) { if openN n closedN n { res append(res, strings.Join(stack, )) return } if openN n { stack append(stack, () backtrack(openN1, closedN) stack stack[:len(stack)-1] } if closedN openN { stack append(stack, )) backtrack(openN, closedN1) stack stack[:len(stack)-1] } } backtrack(0, 0) return res }class Solution { fun generateParenthesis(n: Int): ListString { val stack mutableListOfString() val res mutableListOfString() fun backtrack(openN: Int, closedN: Int) { if (openN n closedN n) { res.add(stack.joinToString()) return } if (openN n) { stack.add(() backtrack(openN 1, closedN) stack.removeAt(stack.lastIndex) } if (closedN openN) { stack.add()) backtrack(openN, closedN 1) stack.removeAt(stack.lastIndex) } } backtrack(0, 0) return res } }class Solution { func generateParenthesis(_ n: Int) - [String] { var stack [Character]() var res [String]() func backtrack(_ openN: Int, _ closedN: Int) { if openN n closedN n { res.append(String(stack)) return } if openN n { stack.append(() backtrack(openN 1, closedN) stack.removeLast() } if closedN openN { stack.append()) backtrack(openN, closedN 1) stack.removeLast() } } backtrack(0, 0) return res } }impl Solution { pub fn generate_parenthesis(n: i32) - VecString { let mut res vec![]; let mut stack String::new(); fn backtrack(open_n: i32, closed_n: i32, n: i32, res: mut VecString, stack: mut String) { if open_n n closed_n n { res.push(stack.clone()); return; } if open_n n { stack.push((); backtrack(open_n 1, closed_n, n, res, stack); stack.pop(); } if closed_n open_n { stack.push()); backtrack(open_n, closed_n 1, n, res, stack); stack.pop(); } } backtrack(0, 0, n, mut res, mut stack); res } }复杂度分析时间复杂度$O(\frac{4^n}{\sqrt{n}})$。这恰好等于最终生成的合法括号串总数第 n 个卡特兰数 $C_n \frac{1}{n1}\binom{2n}{n}$因为回溯只访问「合法前缀」构成的节点空间复杂度$O(n)$。递归深度最多为2n只保存一条当前路径。从源码看回溯的两种写法对比本仓库各语言的实现可以观察到两种风格它们与「可变 vs 不可变」的字符串构建方式直接相关写法一可变构建器 显式撤销backtrackPythonpython/0022-generate-parentheses.py、Javajava/0022-generate-parentheses.java、Gogo/0022-generate-parentheses.go均采用stack列表/栈 递归后pop()撤销的方式只在最终结果处一次性拼接字符串。Go 实现还额外封装了一个pop辅助函数Go 语言没有内置 pop通过切片截断*list (*list)[:length-1]完成撤销详见 go/0022-generate-parentheses.go。写法二不可变字符串拼接 隐式回溯Rubyruby/0022-generate-parentheses.rb和 Rustrust/0022-generate-parentheses.rs采用每次递归传入pre (/pre )的新字符串。由于每次递归都产生新的不可变字符串天然无需撤销逻辑更简洁代价是每层递归都要复制字符串。值得注意的是 Rust 实现rust/0022-generate-parentheses.rs还展示了另一种递归视角从「还剩多少个括号可用」出发递减计数——以(open, close) (n, n)起步open close时只能加左括号否则按剩余量分别尝试加左/右括号当两个计数器都归零时得到一条完整路径。这与「从 0 递增计数」的写法在数学上完全等价可作为交叉验证。进阶变体迭代栈与 BFS仓库中的 C 文件cpp/0022-generate-parentheses.cpp额外给出了不使用递归的显式栈版本栈元素为{当前字符串, 左括号数, 右括号数}初始压入{(, 1, 0}循环弹出、按同样两条安全规则扩展left n right n时输出。该文件注释标注其时间 $O(2^n)$、空间 $O(n)$。JavaScript 文件javascript/0022-generate-parentheses.js则提供了DFS、BFS、递归组合三种实现其中 BFS 版本用队列以[str, open, close]三元组逐层扩展入队条件与回溯完全一致isOpen open n、isClose close open可作为理解「同一剪枝规则既适用于深度优先也适用于广度优先」的绝佳例子。该文件同时也给出了解法三的递归组合写法generateParenthesis(c)generateParenthesis(n - 1 - c)与下面的动态规划思路互相印证。解法三动态规划Dynamic Programming核心直觉一条合法的括号串可以由更小的合法括号串组合而成。观察如下结构( left ) rightleft是含i对括号的合法串right是含k - i - 1对括号的合法串用()包住left可保证平衡拼接上right后整体依然合法。因此k对括号的所有合法结果都可以通过组合更小规模问题的答案得到。这就是卡特兰数的递推结构$C_{k} \sum_{i0}^{k-1} C_i \cdot C_{k-i-1}$。算法步骤令dp[x]存储含x对括号的所有合法字符串基准情形dp[0] []空串对每个k从1到n尝试所有切分点i从0到k-1组合( dp[i] ) dp[k - i - 1]将所有组合存入dp[k]返回dp[n]。多语言实现原文档给出的 DP 版 9 语言实现class Solution: def generateParenthesis(self, n): res [[] for _ in range(n1)] 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]public class Solution { public ListString generateParenthesis(int n) { ListListString res new ArrayList(); for (int i 0; i n; i) { res.add(new ArrayList()); } res.get(0).add(); for (int k 0; k n; k) { for (int i 0; i k; i) { for (String left : res.get(i)) { for (String right : res.get(k - i - 1)) { res.get(k).add(( left ) right); } } } } return res.get(n); } }class Solution { public: vectorstring generateParenthesis(int n) { vectorvectorstring res(n 1); res[0] {}; for (int k 0; k n; k) { for (int i 0; i k; i) { for (const string left : res[i]) { for (const string right : res[k - i - 1]) { res[k].push_back(( left ) right); } } } } return res[n]; } };class Solution { /** * param {number} n * return {string[]} */ generateParenthesis(n) { const res Array.from({ length: n 1 }, () []); res[0] []; for (let k 0; k n; k) { for (let i 0; i k; i) { for (const left of res[i]) { for (const right of res[k - i - 1]) { res[k].push(( left ) right); } } } } return res[n]; } }public class Solution { public Liststring GenerateParenthesis(int n) { ListListstring res new ListListstring(); for (int i 0; i n; i) { res.Add(new Liststring()); } res[0].Add(); for (int k 0; k n; k) { for (int i 0; i k; i) { foreach (string left in res[i]) { foreach (string right in res[k - i - 1]) { res[k].Add(( left ) right); } } } } return res[n]; } }func generateParenthesis(n int) []string { res : make([][]string, n1) res[0] []string{} for k : 1; k n; k { res[k] make([]string, 0) for i : 0; i k; i { for _, left : range res[i] { for _, right : range res[k-i-1] { res[k] append(res[k], ( left ) right) } } } } return res[n] }class Solution { fun generateParenthesis(n: Int): ListString { val res Array(n 1) { mutableListOfString() } res[0] mutableListOf() for (k in 1..n) { for (i in 0 until k) { for (left in res[i]) { for (right in res[k-i-1]) { res[k].add(( left ) right) } } } } return res[n] } }class Solution { func generateParenthesis(_ n: Int) - [String] { var res [[String]](repeating: [], count: n 1) res[0] [] for k in 0...n { for i in 0..k { for left in res[i] { for right in res[k - i - 1] { res[k].append(( left ) right) } } } } return res[n] } }impl Solution { pub fn generate_parenthesis(n: i32) - VecString { let n n as usize; let mut res: VecVecString vec![vec![]; n 1]; res[0] vec![String::new()]; for k in 1..n { let mut cur vec![]; for i in 0..k { let left res[i].clone(); let right res[k - i - 1].clone(); for l in left { for r in right { cur.push(format!(({}){}, l, r)); } } } res[k] cur; } res[n].clone() } }复杂度分析时间复杂度$O(\frac{4^n}{\sqrt{n}})$与回溯法一致同样等于最终结果集的大小空间复杂度$O(n)$不含输出结果本身若把dp表计入则为 $O(\frac{4^n}{\sqrt{n}})$。动态规划 vs 回溯怎么选维度回溯Backtracking动态规划DP构建方式自顶向下逐字符构造边走边剪枝自底向上由小规模答案拼出大规模答案输出顺序取决于分支顺序先左后右按dp[i]与dp[k-i-1]的存储顺序空间仅一条路径 结果$O(n)$需缓存全部中间规模的答案适用场景路径类、组合类生成问题结果可由子结果组合、存在重叠子问题两者时间复杂度的数量级相同回溯更节省中间缓存空间而 DP 的递推式( left ) right更贴近卡特兰数的数学本质。当题目允许「去重」「计数」等变体时DP 往往更容易扩展。常见陷阱Common Pitfalls原文档总结了三个最容易出错的地方这里结合仓库实现逐一说明1. 添加右括号的条件写错添加)的条件是close open而不是close n。右括号只有在存在未匹配的左括号时才能添加若误用close n会生成())(()这类右括号先于其配对左括号出现的非法字符串。可以对比 ruby/0022-generate-parentheses.rb 与 python/0022-generate-parentheses.py两者的剪枝条件都严格写成closes opens/closedN openN。2. 使用可变构建器时忘记回溯使用列表或StringBuilder这类可变结构构建字符串时递归返回后必须移除最后添加的字符pop()/deleteCharAt/removeLast。忘记撤销会导致后续分支的字符串被污染。原文档同时指出不可变字符串拼接如 JS/C# 的stack (虽然天然安全但每层都要复制字符串内存效率更低。3. 误解基准情形条件基准情形应显式检查open n close n而不是只检查length 2n。虽然对合法路径而言二者数学等价但显式检查两个计数器逻辑更清晰也能在分支条件写错时尽早暴露问题——如果非法串因错误分支到达长度2n只检查长度会直接放行错误结果。仓库实现汇总与延伸阅读本仓库在 12 种语言下均提供了该题的独立实现路径统一为0022-generate-parentheses.*Python回溯 显式 pop最贴近本文标准模板C递归回溯 显式栈迭代两种版本Java基于StackCharacter与成员变量的回溯JavaScriptDFS / BFS / 递归组合三种实现Go切片模拟栈 自定义pop辅助函数Ruby不可变字符串拼接天然免撤销Rust递减计数 不可变字符串的另一种回溯视角以及 C、C#、Kotlin、Swift、TypeScript 版本见 c/0022-generate-parentheses.c、csharp/0022-generate-parentheses.cs、kotlin/0022-generate-parentheses.kt、swift/0022-generate-parentheses.swift、typescript/0022-generate-parentheses.ts。配合阅读 hints/generate-parentheses.md 可快速回顾思路脉络Hint 1 指出暴力法的低效Hint 2 引导思考「什么导致字符串非法」Hint 3 点明close open即非法、应维护双计数器剪枝——这正是回溯解法从暴力法自然演进的完整逻辑链。如果你想进一步巩固「递归生成合法组合」这一类问题的解法本仓库中以下文章与本题思路高度同源combinations.md组合与 permutations.md全排列回溯 撤销选择的标准框架word-break.md 与 unique-binary-search-trees.md与本题同属卡特兰数/组合计数结构validate-parentheses.md只校验单一字符串合法性对应本文暴力法的valid函数可作为回溯剪枝条件的数学依据。掌握从「暴力枚举 → 回溯剪枝 → 动态规划」的递进路径后你可以用同一套方法论应对所有「生成所有合法组合」类题目先写出不剪枝的枚举再归纳出合法性的局部判定条件完成剪枝最后尝试用子问题组合描述递推关系。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考