企业官网建设流程全解析

LeetCode 22. 括号生成（Generate Parentheses）：回溯 + 剪枝的多语言题解

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇技术指南以 leetcode 仓库中的 problems/22.generate-parentheses.md 为核心，深入讲解 LeetCode 22「括号生成」的 DFS/回溯解法：从问题建模、剪枝设计到 JS / Python / CPP 三种语言的完整实现与复杂度分析。读完本文，你将掌握一类"构造型"回溯题的通用模板（如何从空串开始做加法、如何用状态参数替代撤销操作），并能将同一套思路迁移到 20. 有效括号、301. 删除无效的括号 等关联题目。

题目描述与题意

数字n代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例：

输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

当n = 3时，一共恰好有 5 种有效组合。需要特别注意的是，题目要求的是"所有可能的有效组合"，因此像"())("、")()("这类右括号先出现、或括号数失衡的字符串都必须被排除在外。这与 problems/22.generate-parentheses.md 中给出的示例输出完全一致。

前置知识

原文档明确列出本解法的两个前置知识：

• DFS（深度优先搜索）：DFS 沿着树的深度尽可能深地搜索分支，搜索到叶子节点后再回溯，是图论中的经典算法。在算法题语境下，搜索中的 DFS 一般指通过递归函数实现暴力枚举。关于 DFS 的算法流程与模板，可以参考仓库的 thinkings/DFS.md。
• 回溯法（Backtracking）：回溯是 DFS 中的一种技巧，采用"试错"思想，分步求解；当发现当前分步答案无法得到有效解答时，就取消上一步乃至上几步的计算，再通过其他可能的分步继续尝试。通俗讲，回溯就是"走不通就回头"的算法。仓库的 thinkings/backtrack.md 对该思想有完整阐述：回溯的本质是穷举所有可能（尽管可以通过剪枝去除不可能成为答案的分支），可以抽象为一棵高度有限的 N 叉树。

本题是 20. 有效括号 的升级版：20 题是判断一个给定字符串是否有效（用栈 $O(N)$ 扫描即可），而 22 题是生成所有有效组合——从"验证"变为"构造"，穷举量呈指数级增长，这正是回溯大展身手的场景。

思路：为什么这道题想到回溯

由于需要求解所有可能的有效组合，回溯就不难想到。回溯的思路和写法相对比较固定，而回溯的优化手段大多是剪枝——即提前终止那些根本不可能是答案的分支，避免无效递归。

对于括号生成问题，一个朴素的想法是：从空字符串出发，每一步可以选择追加一个左括号或右括号，穷举出 $2^{2n}$ 种候选串，再逐一用 20 题的栈方法验证有效性。但这样做浪费巨大，因为大量候选串（如")))((("）在很早的位置就已经注定无效。回溯 + 剪枝的价值正在于此：在构造过程中实时检测非法状态，一旦非法立即返回，不继续向下构造。

剪枝条件：左括号数小于右括号数

不难想到，如果当前路径中左括号的数目小于右括号的数目，我们就可以提前退出，这就是这道题的剪枝。

例如())....，构造到第 3 个字符时，左括号 1 个、右括号 2 个，任何以())开头的字符串都不可能再变成合法括号序列（无论后面怎么补，都会存在一个无法匹配的多余右括号），因此后面就不用看了，直接退出即可。

退出条件（递归边界）

回溯的退出条件也不难想到，即同时满足：

• 左括号数目等于右括号数目
• 左括号数目 + 右括号数目 = 2 × n

也就是说，左右括号各用完了n个，此时路径中的字符串就是一个完整的有效括号组合，将其加入结果集。

为什么必须从左开始遍历（WHY？）

原文档在此处抛出一个值得思考的问题：由于我们需要剪枝，因此必须从左开始遍历（即从空字符串''开始，逐步向右追加字符）。原因是：

1. 括号的有效性判定是前缀相关的：任何合法括号序列的任意前缀，其左括号数都必须不小于右括号数。因此只有"从左到右"逐位构造，才能在构造的每一步都检查l < r这个前缀条件并立即剪枝；
2. 如果跳过前缀、从中间某个位置开始随机填充，l与r的统计就失去了前缀意义，剪枝条件便无法成立，也就退化为无剪枝的盲目枚举。

核心设计：状态做加法，而非维护剩余量

本题使用深度优先搜索（回溯思想），从空字符串开始构造，做加法，即：

dfs(左括号数, 右括号数, 路径)

我们从dfs(0, 0, '')开始。状态由三个变量刻画：

每层递归有两个可选的"动作"：

• 加一个左括号：dfs(l + 1, r, s + '(')；
• 加一个右括号：dfs(l, r + 1, s + ')')。

需要注意，这里的计数是"已使用数量做加法"（从 0 递增到 n），与另一种"剩余数量做减法"（从 n 递减到 0）是等价的视角，本仓库的 CPP 实现即采用了剩余量减法版本，两种写法均可。

伪代码

原文档给出的伪代码如下：

res = [] def dfs(l, r, s): if l > n or r > n: return if (l == r == n): res.append(s) # 剪枝，提高算法效率 if l < r: return # 加一个左括号 dfs(l + 1, r, s + '(') # 加一个右括号 dfs(l, r + 1, s + ')') dfs(0, 0, '') return res

伪代码中的四层防护清晰对应四个要素：越界保护（l > n or r > n）、目标收集（l == r == n）、剪枝（l < r）、递归展开（追加左 / 右括号）。

字符串不可变语言：无需撤销操作

一个容易被忽视的语言细节：由于 Python、JavaScript 等语言中字符串是不可变的（immutable），每次s + '('都会生成新的字符串传入下一层递归，当前层的s并不会被修改，因此我们无需"撤销 s 的选择"。

但当你使用 C++ 等语言时，字符串是可变对象，若通过引用传递并原地修改，就需要注意在递归返回后撤销刚才的修改，否则状态会污染兄弟分支。类似这样：

s.push_back(')'); dfs(l, r + 1, s); s.pop_back();

push_back之后必须pop_back恢复现场，这正是 thinkings/backtrack.md 中强调的要点：回溯通常把结果记录在搜索路径上，如果不进行撤销操作，回溯后状态不正确会导致结果差异；而如果每次递归都拷贝一份数据，就不需要撤销，代价是空间复杂度增加。

关键点

• 当l < r时记得剪枝：这是本题唯一的剪枝，也是能否高效通过的关键；
• 剪枝的时机依赖"从左到右"的构造顺序，见前文 WHY 分析；
• 在不可变字符串语言中免去撤销操作，在可变字符串语言（如 C++）中务必配对push_back/pop_back。

代码实现（JS / Python / CPP）

原文档指出语言支持：JS，Python3，CPP。以下三份代码均直接来自 problems/22.generate-parentheses.md，可直接复制运行。

JS Code

/** * @param {number} n * @return {string[]} * @param l 左括号已经用了几个 * @param r 右括号已经用了几个 * @param str 当前递归得到的拼接字符串结果 * @param res 结果集 */ const generateParenthesis = function (n) { const res = []; function dfs(l, r, str) { if (l == n && r == n) { return res.push(str); } // l 小于 r 时不满足条件 剪枝 if (l < r) { return; } // l 小于 n 时可以插入左括号，最多可以插入 n 个 if (l < n) { dfs(l + 1, r, str + "("); } // r < l 时 可以插入右括号 if (r < l) { dfs(l, r + 1, str + ")"); } } dfs(0, 0, ""); return res; };

JS 版本用if (l < n)显式限制左括号上限，用if (r < l)天然满足"右括号不超过左括号"的约束，配合l < r剪枝，三重保障确保只产出合法序列。

Python Code

class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] def dfs(l, r, s): if l > n or r > n: return if (l == r == n): res.append(s) if l < r: return # 加一个左括号 dfs(l + 1, r, s + '(') # 加一个右括号 dfs(l, r + 1, s + ')') dfs(0, 0, '') return res

Python 版本完整对应伪代码，写法最简，适合作为回溯模板背诵。

CPP Code

class Solution { private: vector<string> ans; void generate(int leftCnt, int rightCnt, string &s) { if (!leftCnt && !rightCnt) { ans.push_back(s); return; } if (leftCnt) { s.push_back('('); generate(leftCnt - 1, rightCnt, s); s.pop_back(); } if (rightCnt > leftCnt) { s.push_back(')'); generate(leftCnt, rightCnt - 1, s); s.pop_back(); } } public: vector<string> generateParenthesis(int n) { string s; generate(n, n, s); return ans; } };

CPP 版本采用了"剩余量减法"视角：leftCnt、rightCnt初始为n，递减到 0 即为完成；剪枝条件等价于rightCnt > leftCnt（剩余右括号多于剩余左括号时不允许放右括号）；string &s以引用传递并原地修改，因此每次递归返回后都配对了pop_back()撤销，体现了可变字符串语言中"回溯必须撤销"的规范写法。

复杂度分析

原文档给出的复杂度如下：

• 时间复杂度：O(2^N)
• 空间复杂度：O(2^N)

更精确地看，解空间的大小正是第 n 个卡特兰数（Catalan Number）：$C_n = \frac{1}{n+1}\binom{2n}{n}$。例如n = 3时 $C_3 = 5$，与示例输出中的 5 种组合吻合。因此剪枝后的实际搜索节点数约为 $O(C_n)$，整体复杂度可记为 $O(\frac{4^n}{\sqrt{n}})$ 量级，指数级增长意味着n稍大时只能依赖剪枝压缩搜索树。仓库中 problems/95.unique-binary-search-trees-ii.md 同样以"令 C(N) 为 N 的卡特兰数"来刻画复杂度，可见卡特兰数是这类"所有合法结构"计数问题的共同数学背景。

回溯模板在本仓库中的印证

将本题的实现与仓库的算法专题对照，可以清晰看到它完全遵循 thinkings/backtrack.md 总结的回溯流程：

1. 构造空间树：本题的空间树是一棵高度为2n的二叉树，每个节点代表一个"前缀 + 左右括号选择"的状态，从根节点('')到叶子的每条路径对应一个候选组合；
2. 进行遍历：DFS 前序遍历，先尝试加左括号再尝试加右括号；
3. 遇到边界条件不再向下搜索：l < r剪枝、l == n && r == n到达叶子；
4. 达到目标条件输出结果：左右括号都用完时res.push(str)。

在 thinkings/backtrack.md 的经典题目清单中，与本题同属"构造型回溯"的还有 39. 组合总和、46. 全排列、78. 子集、131. 分割回文串 等，它们的共同点是：结果集记录在递归路径上，需要处理好状态撤销（或利用不可变对象规避撤销）。

关联题目与扩展

• 20. 有效括号：本题的验证版前身。用栈遍历字符串即可判断有效性，复杂度 O(N)；仓库中该文档还给出了 O(1) 空间（原地修改参数模拟栈）与正则消消乐等扩展解法。理解 20 题的"前缀左括号数 ≥ 右括号数"判定规则，是理解 22 题剪枝条件的基础。
• 301. 删除无效的括号：反向变体——给定一个含无效括号的字符串，要求删除最少数量的括号使其有效并返回所有结果。由于要求"删除最少"，该题优先选择广度优先遍历（BFS）+ 队列 + visited 去重，而非本题的 DFS，这种"同主题、不同遍历策略"的对比值得反复体会。
• 卡特兰数家族：括号序列、出栈序列、二叉搜索树形态等问题的计数都与卡特兰数相关，可参考仓库中 95. 不同的二叉搜索树 II 的复杂度分析进行横向对比。

总结

括号生成是一道经典的"构造型回溯"题目，其解题要点可归纳为：

1. 从空串做加法：用dfs(l, r, s)三元状态逐步构造，而非一次性枚举后验证；
2. 一条剪枝走天下：只要l < r立即返回，配合l == n && r == n的终止条件，即可保证所有输出都是有效组合；
3. 留意语言差异：不可变字符串免撤销，可变字符串（C++）必须在递归返回后pop_back恢复现场；
4. 复杂度牢记卡特兰数：答案数量为第 n 个卡特兰数，指数增长，剪枝必不可少。

掌握了本题的"前缀合法性剪枝"思想后，你可以将其推广到任意"部分解必须是合法前缀"的生成类问题中，配合仓库 thinkings/backtrack.md 与 thinkings/DFS.md 两个专题继续加深理解。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode