doocs/leetcode 中 LeetCode 22 括号生成题解：DFS + 剪枝回溯的完整实现与多语言源码解析-平芜编程栈

示例工程

【免费下载链接】leetcode

🔥LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

本篇指南基于 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$ 个卡特兰数同量级（$n=3$ 时恰好生成 5 个合法串，与示例一致），剪枝正是让实际运行远小于该上界的原因。

多语言参考实现

以下是题解文档给出的全部实现，与仓库中各语言源文件逐行对应（对照关系见下一节）。

Python3

class 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 ans

Java

class Solution { private List<String> ans = new ArrayList<>(); private int n; public List<String> 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 + ")"); } }

C++

class Solution { public: vector<string> generateParenthesis(int n) { vector<string> 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; } };

Go

func 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(l+1, r, t+"(") dfs(l, r+1, t+")") } dfs(0, 0, "") return ans }

TypeScript

function 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; }

Rust

impl Solution { pub fn generate_parenthesis(n: i32) -> Vec<String> { let mut ans = Vec::new(); fn dfs(ans: &mut Vec<String>, 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 List<string> ans = new List<string>(); private int n; public List<string> 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 + ")"); } }

PHP

class 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 / JavaScript：dfs是定义在函数体内的闭包，ans与n通过词法作用域共享；
Java / C# / PHP：dfs写成类的私有方法，ans与n是实例字段（PHP 在入口处把两者显式重置，避免多次调用间状态残留）；
C++：使用 C++20 通用 lambda（this auto&& dfs参数写法）实现自引用递归，无需额外成员变量；
Go：用命名返回值(ans []string)作为收集容器，dfs通过函数类型变量先声明后赋值实现自引用；
Rust：dfs是普通嵌套函数，显式通过&mut Vec<String>借用答案切片，t以String值传递并用format!拼接。

仓库源码对照验证

题解目录solution/0000-0099/0022.Generate Parentheses/下与文档配套的源文件为：

Solution.py
Solution.java
Solution.cpp
Solution.go
Solution.ts
Solution.js
Solution.rs
Solution.cs
Solution.php

从源码结构看，各源文件与题解文档中的内嵌代码一一对应，可以直接作为 LeetCode 提交格式使用（Solution类 +generateParenthesis方法）。以 Solution.py 为例：第 4 行就是三条件剪枝出口if l > n or r > n or l < r，第 6～8 行是 $l = r = n$ 的终止出口，第 9～10 行是两条递归分支，与文档描述的递归结构逐条吻合；Solution.java 的私有方法dfs(int l, int r, String t)同样在第 12 行实现剪枝、第 19～20 行展开两个分支。

小结

本题的关键是把“合法前缀”的性质压缩为两个计数器：任何时刻必须满足 $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）逻辑完全一致，可直接在题解目录下对照查阅，作为回溯 + 剪枝写法在多语言间的参照实现。