1. 题目大意
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
2. 直观理解：存钱 vs 花钱
要生成有效的括号，我们可以把 ( 看作存钱，把 ) 看作花钱。
假设 n=3，意味着你总共有 3 枚金币的额度。要完成这个游戏，必须遵守两条极其简单的规则：
- 总额度限制：
你最多只能存n次钱。只要存入次数没达到n，你随时可以存（加左括号）。 - 余额限制：
想花钱，前提是你账户里得有钱。也就是说，当前存入的次数必须大于当前花出的次数，你才能花钱（加右括号）。
游戏目标：把这 n 枚金币全部存进去，再全部花完，中间不能透支。
3. 算法核心：二叉树与剪枝
如果我们把每一步的选择画出来，它就像一棵二叉树。每一个节点，我们都面临两个选择：是放 ( 还是放 ) ？
但是，为了保证结果“有效”，我们不能盲目地生成所有组合（那是 2^2n 种，太多且包含非法结果），我们需要在树生长的时候进行剪枝。
我们需要记录三个状态：
s：当前拼接的字符串。left：已经放了多少个左括号。right：已经放了多少个右括号。
决策逻辑：
- 左分支（加左括号）：只要
left < n，这个分支就是通的。 - 右分支（加右括号）：只有
right < left，这个分支才是通的。
4. 给不懂递归的你：外包与分身术
如果你觉得递归难以理解，请把 backtrack 函数想象成“把任务外包给分身”。
假设你是 0号员工（大老板），你的任务是填满 $2n$ 个格子。
你很懒，你只做当前这一步的决定，剩下的工作你复制一个和你一模一样的分身（下级员工）去干。
场景模拟（n=2）：
- 你（0号）：手里拿着空纸条
""。你决定写个(，纸条变成(。然后你变出 1号员工，把纸条交给他，让他去处理剩下的。 - 1号员工：拿着
(。他发现还可以写(，于是写上，变成((。他变出 2号员工 交接工作。 - 2号员工：拿着
((。他发现不能写(了（额度用完了），只能写)。纸条变成(()。交接给 3号员工。 - ...
- 4号员工：拿着
(())。他发现长度够了，把结果扔进信箱，然后下班（消失）。
什么是回溯（Backtracking）？
当 4号员工 消失后，时空回到了 3号员工 刚才做决定的那一刻。3号员工会想：“刚才那条路走完了，我还有别的选择吗？没有了，我也下班。”
...
一直回到 1号员工。1号员工会想：“刚才我选择了加左括号 ((，那条路已经被分身跑通了。但我其实当时还可以选择加右括号 () 啊！”
于是，1号员工会立刻派出另一个分身，去尝试 () 这条新路。
这就是递归：一大群分身在帮你把所有迷宫的路都试一遍，撞墙了就回头，走出去了就记录。
5. 代码实现
Python 版本
Python 的代码最为简洁，因为字符串是不可变的，在递归传递 s + "(" 时，自动创建了新对象，相当于天然自带了“回溯撤销”的功能。
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
# s: 当前的字符串
# left: 左括号用了几个
# right: 右括号用了几个
def backtrack(s, left, right):
# 【终止条件】
# 存了n次，也花了n次，总长度达到2n，任务完成
if len(s) == 2 * n:
res.append(s)
return
# 【选择 1】尝试加左括号 (存钱)
if left < n:
backtrack(s + "(", left + 1, right)
# 【选择 2】尝试加右括号 (花钱)
# 核心逻辑：只有余额(left) > 支出(right) 才能花
if right < left:
backtrack(s + ")", left, right + 1)
# 启动递归
backtrack("", 0, 0)
return res
Java 版本
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(res, "", 0, 0, n); // 初始传入空字符串
return res;
}
private void backtrack(List<String> res, String cur, int left, int right, int max) {
// 终止条件
if (cur.length() == max * 2) {
res.add(cur);
return;
}
// 尝试加左括号
if (left < max) {
// 【关键点】直接传入 cur + "("
// 这会创建一个新的字符串对象传递给下一层
// 本层的 cur 并没有改变，所以不需要撤销
backtrack(res, cur + "(", left + 1, right, max);
}
// 尝试加右括号
if (right < left) {
// 同理，直接传入 cur + ")"
backtrack(res, cur + ")", left, right + 1, max);
}
}
}总结
解决“括号生成”问题的关键在于不要被“有效组合”这个词吓倒。记住那两个简单的规则：
- 左括号没满就能加。
- 右括号比左括号少就能加。
剩下的，就交给递归函数（你的分身们）去跑完所有可能的分支吧！