Generate Parentheses 是 LeetCode Hot 100 里面一道非常经典的回溯题。
这道题和前面的“电话号码的字母组合”有点像，都是通过递归一层层构造答案；但它又比电话号码题多了一层限制： 不是随便拼接字符就行，而是必须保证最终生成的括号序列是 合法的括号组合。
也正因为有了这个“合法性约束”，这道题就成了学习 回溯 + 剪枝 的非常典型的一题。很多人第一次学回溯时，往往只是会写“枚举所有情况”；而这道题真正重要的地方在于： 我们不是先把所有字符串都生成出来再筛选，而是在生成过程中就主动避免无效情况。
你给出的这份 Java 代码，就是这道题最经典的回溯写法之一。 本文就结合这段代码，系统地讲一下这道题的思路。
题目介绍
给定一个整数 n，要求你生成所有由 n 对括号组成的、并且合法的括号组合。
例如：
n = 3
那么答案是：
["((()))","(()())","(())()","()(())","()()()"]
注意，这里要求的是：
-
一共必须有
n个左括号( -
一共必须有
n个右括号) -
并且整个括号字符串必须是合法的
所谓合法，意思是任意前缀中，左括号的数量都不能少于右括号的数量，并且最终左右括号数量相等。
比如：
-
"(()())"是合法的 -
"())(()"不合法 -
")("不合法 -
"((("也不合法
所以这道题的难点并不是“怎么拼出长度为 2n 的字符串”，而是“怎么只生成合法答案”。
示例
示例 1
输入：n = 1 输出：["()"]
只有一对括号时，唯一合法的结果就是：
"()"
示例 2
输入：n = 2 输出：["(())","()()"]
两对括号时，一共只有两种合法情况。
示例 3
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
这也是这道题最经典的示例。
这道题为什么适合用回溯？
因为这道题本质上是一个“逐步构造答案”的过程。
假设我们现在要生成一个长度为 2n 的括号字符串。 那每一步其实只有两种选择：
-
放一个左括号
"(" -
放一个右括号
")"
也就是说，我们可以把整个过程想成一棵决策树：
-
每一层表示当前要放第几个字符
-
每个结点都有最多两种选择：放左括号或放右括号
-
当字符串长度达到
2n时，就得到一个完整结果
这就是典型的回溯模型。
但是和普通“全排列”不同的是，这里并不是所有路径都合法。 所以我们需要在回溯过程中加上限制条件，也就是所谓的 剪枝。
最朴素的想法为什么不好？
如果完全不考虑剪枝，那么我们可能会想到：
-
一共需要生成长度为
2n的字符串 -
每一位都可以是
(或) -
所以总共有
2^(2n)种可能
然后我们再把这些字符串一个个检查，筛出合法答案。
这个方法当然理论上可行，但效率很差。 因为绝大多数生成出来的字符串都是无效的，我们做了大量没有必要的工作。
比如 n = 3 时，长度是 6，所有可能字符串有：
2^6 = 64
种，但真正合法的结果只有 5 个。
所以更好的思路是：
在构造过程中，一旦发现某条路径不可能合法，就立刻停止继续搜索。
这正是回溯的优势所在。
核心思路
我们在递归过程中维护三个信息：
-
current：当前已经构造出的括号字符串 -
open：当前已经使用了多少个左括号 -
close：当前已经使用了多少个右括号
然后根据这三个量来决定下一步能做什么。
情况 1：还能继续放左括号
只要当前使用的左括号数量还没有达到 n，就可以继续加左括号：
if (open < n)
情况 2：还能继续放右括号
右括号不能乱放。 只有当前已经放置的右括号数量 小于 左括号数量时，才能放右括号：
if (close < open)
为什么？
因为如果某一时刻右括号数量超过了左括号数量，那么当前前缀一定不合法。 而一个不合法的前缀，不可能再补救成合法答案。
这就是这道题最关键的剪枝条件。
Java 代码
下面是你给出的代码，我这里保留原本逻辑，并加上注释：
class Solution {
List<String> combinations = new ArrayList<>();
public List<String> generateParenthesis(int n) {
backtrack("", 0, 0, n);
return combinations;
}
public void backtrack(String current, int open, int close, int max) {
// 如果当前字符串长度已经达到 2 * n，说明构造完成
if (current.length() == max * 2) {
combinations.add(current);
return;
}
// 只要左括号数量还没达到上限，就可以继续放左括号
if (open < max)
backtrack(current + "(", open + 1, close, max);
// 只有右括号数量小于左括号数量时，才可以放右括号
if (close < open)
backtrack(current + ")", open, close + 1, max);
}
}
代码拆解
这段代码虽然不长，但它把回溯的核心结构和剪枝条件都体现得非常完整。 下面一步一步来看。
1. generateParenthesis 做了什么？
public List<String> generateParenthesis(int n) {
backtrack("", 0, 0, n);
return combinations;
}
这个函数只是做了两件事：
-
从空字符串开始递归
-
返回最终结果列表
一开始：
-
当前字符串是
"" -
已使用左括号数
open = 0 -
已使用右括号数
close = 0
然后通过递归不断扩展。
2. backtrack 里的参数分别表示什么？
public void backtrack(String current, int open, int close, int max)
这四个参数非常关键：
-
current：当前已经拼出来的括号字符串 -
open：当前已经放了多少个左括号 -
close：当前已经放了多少个右括号 -
max：一共需要放多少对括号，也就是n
换句话说，这个函数表示的是：
当前已经生成了一个部分括号串 current，其中用了 open 个左括号、close 个右括号，接下来继续补全它。
只要把这个定义想明白，后面的递归逻辑就非常清楚了。
3. 为什么长度到 2 * n 就可以加入答案？
if (current.length() == max * 2) {
combinations.add(current);
return;
}
因为一个由 n 对括号组成的字符串，总长度一定是：
2 * n
所以当 current.length() 达到这个长度时，说明我们已经放完了全部括号。
而由于前面每一步都遵守了合法性条件，所以能走到这里的字符串一定是合法答案，可以直接加入结果集。
4. 为什么 open < max 时可以继续放左括号？
if (open < max)
backtrack(current + "(", open + 1, close, max);
因为总共只允许放 n 个左括号。
所以只要当前已经使用的左括号数量还没达到上限，就可以继续添加一个左括号。
这一步很好理解，本质上是在控制左括号总数不能超标。
5. 为什么 close < open 时才能放右括号？
if (close < open)
backtrack(current + ")", open, close + 1, max);
这是整道题最核心的一句。
因为括号是否合法，有一个非常重要的性质：
在任意前缀中，右括号的数量都不能超过左括号数量。
比如：
-
"()"合法 -
"(())"合法 -
"())"不合法 -
")("不合法
一旦某个前缀出现：
close > open
那么当前字符串一定已经不可能变成合法括号串了。
所以只有在：
close < open
的情况下，才允许继续加右括号。
这就是剪枝。
也正是因为有了这个条件，我们在搜索过程中就能主动避开大量无效路径。
手动模拟一遍
我们用最经典的例子来手动走一遍：
n = 3
初始调用：
backtrack("", 0, 0, 3)
第一步：当前是空串
-
current = "" -
open = 0 -
close = 0
这时候：
-
可以放左括号，因为
open < 3 -
不能放右括号，因为
close < open不成立
所以只能走：
"("
第二步：当前是 "("
-
open = 1 -
close = 0
这时候两种选择都可以：
-
放左括号，变成
"((" -
放右括号，变成
"()"
于是递归会分成两条路。
路线一：继续放左括号
从 "(" 变成：
"(("
再往下又可以继续放左括号，变成：
"((("
然后此时左括号已经用满，只能不断补右括号，最终得到：
"((()))"
路线二：在第二步放右括号
从 "(" 变成：
"()"
接下来还可以继续放左括号，再逐步扩展，会生成：
-
"()(())" -
"()()()"
以及其他合法路径。
最终所有搜索结束后，会得到：
["((()))","(()())","(())()","()(())","()()()"]
这道题的本质是什么？
这道题本质上是在一棵搜索树中寻找所有合法路径。
每一步我们都面临两个选择：
-
加左括号
-
加右括号
但不是每个选择都允许。 我们必须始终维持一个约束：
-
左括号总数不能超过
n -
右括号数量不能超过左括号数量
所以这道题的关键不是“暴力生成所有情况”，而是：
在搜索过程中维持合法状态，只扩展那些仍然有可能成为答案的路径。
这就是典型的回溯 + 剪枝思想。
复杂度分析
时间复杂度
这道题的准确时间复杂度不太适合简单写成 O(2^(2n))，因为我们并没有真的搜索所有长度为 2n 的字符串。
实际生成的答案数量和第 n 个卡特兰数有关。 如果按题解常见写法，可以理解为：
-
回溯会遍历所有合法括号组合
-
每个组合长度为
2n
因此时间复杂度可以近似理解为：
O(Cn * n)
其中 Cn 表示第 n 个卡特兰数。
如果不强调数学公式，也可以直接理解为：
时间复杂度与最终合法答案的数量成正比。
空间复杂度
递归深度最多是：
2n
因此递归栈空间为：
O(n)
如果把结果集也算进去，那么总空间还要加上所有答案本身占用的空间。
这道题真正想考什么？
这道题非常经典，它真正考察的其实有两个层面。
第一，是否理解回溯的基本结构
也就是：
-
定义状态
-
写终止条件
-
枚举当前层选择
-
递归进入下一层
这是一切回溯题的共同骨架。
第二，是否会在回溯中做剪枝
这道题最精彩的地方就在于：
我们并不是生成所有字符串再判断，而是提前利用规则：
-
open < max -
close < open
来限制搜索范围。
所以它比“电话号码的字母组合”更进一步，因为它开始真正体现回溯的效率优势。
和“有效的括号”有什么区别？
很多人在刷题时会把这两题联想到一起：
-
LeetCode 20：有效的括号
-
LeetCode 22：括号生成
它们都和括号有关，但考点其实不同。
有效的括号
考的是：
-
给定一个字符串，判断它是否合法
-
重点数据结构是 栈
括号生成
考的是：
-
构造出所有合法的字符串
-
重点方法是 回溯
一个是在“验证”，一个是在“生成”。
虽然都用到了括号合法性的规则，但解决问题的工具完全不同。
总结
这道题的核心思想可以概括成一句话：
通过回溯逐步构造括号串，并在构造过程中始终保证当前前缀合法。
具体做法就是：
-
用
current记录当前路径 -
用
open记录已经使用的左括号数量 -
用
close记录已经使用的右括号数量 -
当长度达到
2n时，把当前结果加入答案 -
如果左括号还没用完，就继续放左括号
-
如果右括号数量小于左括号数量，就可以放右括号
这道题是一道非常标准、也非常有代表性的回溯题。 它不仅能帮助你掌握“如何写回溯”，更重要的是能让你理解：
真正高效的回溯，不只是搜索，更是在搜索过程中不断剪掉不可能的分支。
如果你把这道题真正理解透，那么后面再去做：
-
组合总和
-
子集
-
全排列
-
N 皇后
这些题时，你会越来越能体会“状态、选择、递归、剪枝”这一整套回溯框架的威力。
