示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇指南基于 doocs/leetcode 仓库中的 LeetCode 22 题解文档完整讲解“括号生成”这道经典回溯题的解题思路如何仅用l左括号数、r右括号数两个状态量对搜索树做剪枝以及仓库中 9 种语言参考实现与文档代码的一一对应关系。读完后你可以直接复用其中的dfs(l, r, t)递归骨架并将同一剪枝思路迁移到组合生成、字符串排列类问题。题目描述与输入输出约定题目要求给定n对括号写一个函数生成所有**格式正确well-formed**的括号组合。示例摘自题解文档输入输出n 3[((())),(()()),(())(),()(()),()()()]n 1[()]约束条件1 n 8。题解文档的元信息标注了本题难度为 Medium标签为String、Dynamic Programming、Backtracking、Parentheses对应中文题解见 中文文档。需要特别注意的边界语义是“合法前缀”的判定一个尚未完成的括号串只要出现以下任一情况后续无论怎么补都救不回来——右括号数超过左括号数前缀中)多于(左括号或右括号的数量超过n。这一点是后文所有剪枝条件的来源。解题思路为什么“暴力搜索 剪枝”就够了题解文档的 Thinking 部分给出的思考路径是朴素方案枚举所有长度为 $2n$ 的括号串保留合法者。$n \le 8$ 时候选串数量上界为 $2^{2n} 2^{16}$其实可以直接通过问题所在绝大多数前缀已经注定非法。一旦某个前缀中)多于(或某侧括号个数超过 $n$就不可能再有合法后缀改进方案一个合法前缀只需要两个计数 $l$已放入的左括号数与 $r$已放入的右括号数来刻画。DFS 每一步尝试追加(或)用三个不等式剪枝保持 $l \ge r$且两者都不超过 $n$当 $l r n$ 时把当前串收入答案。文档原文的结论是“搜索树比全枚举小得多额外空间仅为当前字符串的 $O(n)$。”这正是“回溯 剪枝”这一套路的价值所在——状态空间没有减少但被提前掐死的非法分支大幅减少。DFS 剪枝的递归结构题解文档定义了递归函数 $dfs(l, r, t)$其中 $l$、$r$ 分别表示已使用的左、右括号数量$t$ 表示当前括号序列。递归结构为四条规则若 $l \gt n$ 或 $r \gt n$ 或 $l \lt r$当前组合 $t$ 无效直接返回剪枝出口若 $l n$ 且 $r n$当前组合 $t$ 合法加入答案数组ans直接返回终止出口选择追加左括号递归执行dfs(l 1, r, t ()选择追加右括号递归执行dfs(l, r 1, t ))。文档给出的复杂度结论时间复杂度 $O(2^{n\times 2} \times n)$空间复杂度 $O(n)$。这里的空间复杂度指递归栈上保存当前串 $t$ 的额外开销不计结果数组。可以补充说明$O(2^{n\times 2} \times n)$ 是不剪枝时的搜索树上界实际被访问的状态数与第 $n$ 个卡特兰数同量级$n3$ 时恰好生成 5 个合法串与示例一致剪枝正是让实际运行远小于该上界的原因。多语言参考实现以下是题解文档给出的全部实现与仓库中各语言源文件逐行对应对照关系见下一节。Python3class Solution: def generateParenthesis(self, n: int) - List[str]: def dfs(l: int, r: int, t: str): if l n or r n or l r: return if l n and r n: ans.append(t) return dfs(l 1, r, t () dfs(l, r 1, t )) ans [] dfs(0, 0, ) return ansJavaclass Solution { private ListString ans new ArrayList(); private int n; public ListString generateParenthesis(int n) { this.n n; dfs(0, 0, ); return ans; } private void dfs(int l, int r, String t) { if (l n || r n || l r) { return; } if (l n r n) { ans.add(t); return; } dfs(l 1, r, t (); dfs(l, r 1, t )); } }Cclass Solution { public: vectorstring generateParenthesis(int n) { vectorstring ans; auto dfs - void { if (l n || r n || l r) { return; } if (l n r n) { ans.push_back(t); return; } dfs(l 1, r, t (); dfs(l, r 1, t )); }; dfs(0, 0, ); return ans; } };Gofunc generateParenthesis(n int) (ans []string) { var dfs func(int, int, string) dfs func(l, r int, t string) { if l n || r n || l r { return } if l n r n { ans append(ans, t) return } dfs(l1, r, t() dfs(l, r1, t)) } dfs(0, 0, ) return ans }TypeScriptfunction generateParenthesis(n: number): string[] { const dfs (l: number, r: number, t: string) { if (l n || r n || l r) { return; } if (l n r n) { ans.push(t); return; } dfs(l 1, r, t (); dfs(l, r 1, t )); }; const ans: string[] []; dfs(0, 0, ); return ans; }Rustimpl Solution { pub fn generate_parenthesis(n: i32) - VecString { let mut ans Vec::new(); fn dfs(ans: mut VecString, l: i32, r: i32, t: String, n: i32) { if l n || r n || l r { return; } if l n r n { ans.push(t); return; } dfs(ans, l 1, r, format!({}(, t), n); dfs(ans, l, r 1, format!({}), t), n); } dfs(mut ans, 0, 0, String::new(), n); ans } }JavaScript/** * param {number} n * return {string[]} */ var generateParenthesis function (n) { const dfs (l, r, t) { if (l n || r n || l r) { return; } if (l n r n) { ans.push(t); return; } dfs(l 1, r, t (); dfs(l, r 1, t )); }; const ans []; dfs(0, 0, ); return ans; };C#public class Solution { private Liststring ans new Liststring(); private int n; public Liststring GenerateParenthesis(int n) { this.n n; Dfs(0, 0, ); return ans; } private void Dfs(int l, int r, string t) { if (l n || r n || l r) { return; } if (l n r n) { ans.Add(t); return; } Dfs(l 1, r, t (); Dfs(l, r 1, t )); } }PHPclass Solution { private $ans []; private $n 0; /** * param Integer $n * return String[] */ function generateParenthesis($n) { $this-n $n; $this-ans []; $this-dfs(0, 0, ); return $this-ans; } private function dfs($l, $r, $t) { if ($l $this-n || $r $this-n || $l $r) { return; } if ($l $this-n $r $this-n) { $this-ans[] $t; return; } $this-dfs($l 1, $r, $t . (); $this-dfs($l, $r 1, $t . )); } }各语言实现的核心逻辑完全一致差异仅在“递归闭包/状态”的表达方式上Python3 / TypeScript / JavaScriptdfs是定义在函数体内的闭包ans与n通过词法作用域共享Java / C# / PHPdfs写成类的私有方法ans与n是实例字段PHP 在入口处把两者显式重置避免多次调用间状态残留C使用 C20 通用 lambdathis auto dfs参数写法实现自引用递归无需额外成员变量Go用命名返回值(ans []string)作为收集容器dfs通过函数类型变量先声明后赋值实现自引用Rustdfs是普通嵌套函数显式通过mut VecString借用答案切片t以String值传递并用format!拼接。仓库源码对照验证题解目录solution/0000-0099/0022.Generate Parentheses/下与文档配套的源文件为Solution.pySolution.javaSolution.cppSolution.goSolution.tsSolution.jsSolution.rsSolution.csSolution.php从源码结构看各源文件与题解文档中的内嵌代码一一对应可以直接作为 LeetCode 提交格式使用Solution类 generateParenthesis方法。以 Solution.py 为例第 4 行就是三条件剪枝出口if l n or r n or l r第 68 行是 $l r n$ 的终止出口第 910 行是两条递归分支与文档描述的递归结构逐条吻合Solution.java 的私有方法dfs(int l, int r, String t)同样在第 12 行实现剪枝、第 1920 行展开两个分支。小结本题的关键是把“合法前缀”的性质压缩为两个计数器任何时刻必须满足 $l \ge r$ 且 $l, r \le n$两者同时等于 $n$ 即为一个完整答案递归骨架dfs(l, r, t)只有两条分支全部复杂度控制都集中在开头的三条件剪枝里文档标注的时间复杂度 $O(2^{n\times 2} \times n)$、空间复杂度 $O(n)$ 中空间主要指递归深度携带的当前字符串 $t$仓库内 9 种语言的解法Python3 / Java / C / Go / TypeScript / Rust / JavaScript / C# / PHP逻辑完全一致可直接在 题解目录 下对照查阅作为回溯 剪枝写法在多语言间的参照实现。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode 22「括号生成」DFS 剪枝的回溯解法与多语言实现详解doocs/leetcode 题解LeetCode 22「括号生成」DFS 剪枝的回溯解法与多语言实现详解doocs/leetcode 题解 本篇技术文章基于开源仓库 doocs/le示例工程LeetCode 22 括号生成Generate ParenthesesDFS 剪枝多语言题解与源码解析LeetCode 22 括号生成Generate ParenthesesDFS 剪枝多语言题解与源码解析 本文以 doocs/leetcode 仓库中示例工程LeetCode 22 括号生成Generate ParenthesesDFS 剪枝多语言题解全解析LeetCode 22 括号生成Generate ParenthesesDFS 剪枝多语言题解全解析 本文以 doocs/leetcode 仓库中 L示例工程上一篇终极指南3步让Mem Reduct内存监控工具秒变中文界面下一篇如何快速部署开发环境终极Visual C运行库解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
