22、括号生成
22、括号生成
鲁迅说过，每天刷一道二哥的 LeetCode 题解，感觉精神百倍，工作效率都提高
了（dog）。
题意
数字 n 代表生成括号的对数，请你设计一个方法，用于能够生成所有可能的并且 有效的
括号组合。
• 1 <= n <= 8
难度
中等
示例
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
输入：n = 1
输出：["()"]
分析
什么是有效的括号？例如：
String: "( ( ( ) ) )"
位置 :1 2 3 4 5 6
左括号数量:1 2 3 3 3 3
右括号数量:0 0 0 1 2 3
再例如：
String: "( ( ) ( ) )"
位置 :1 2 3 4 5 6
左括号数量:1 2 2 3 3 3
右括号数量:0 0 1 1 2 3
我们发现，无论在哪个位置，右括号数量都是小于等于左括号的，并且当左括号数量小于
n 时，我们可以无限添加左括号，对吧？
当右括号数量小于左括号数量时，我们可以无限添加右括号。
当括号的数量达到 2n 时，我们就得到了所有的有效括号。
当我们把括号的问题转化成树结构的时候，就可以更直观地理解这个问题。在数结构中，
每个节点代表一个括号组合。
从根节点（空字符串）开始，每一层代表字符串中添加新括号的操作。对于每个节点，它
最多可以有两个子节点：
• 一个代表添加一个左括号(，如果添加后不超过 n 个左括号
• 另外一个代表添加一个右括号)，如果添加后右括号数量小于左括号数量
每一层都比前一层有更多可能的括号组合，等到达到 2n 时，所有路径都是有效的括号组
合。
假设 n = 2 时，我们可以得到如下的树结构：
022.%E6%8B%AC%E5%8F%B7%E7%94%9F%E6%88%90-20240203163724.png
• 在这个树中，根节点是空字符串 ""。
• 第一层有一个节点 "("，代表我们添加可以一个左括号。X 表示我们不能添加右括
号。
• 第二层展示了添加第二个括号时的所有可能性：我们可以再添加另外一个左括号
"("（左括号数量小于 n），或者添加一个右括号 ")"（右括号数量小于左括号数
量）。
• 以此类推，我们可以得到所有的有效括号组合。
class Solution {
List<String> combinations = new ArrayList<>();
// 主方法，调用此函数生成所有的括号组合
public List<String> generateParenthesis(int n) {
backtrack("", 0, 0, n);
return combinations;
}
// 回溯方法
private void backtrack(String current, int open, int close, int max) {
// 如果当前字符串长度等于最大长度的两倍，说明找到了一个解，添加到结果列表中
if (current.length() == max * 2) {
combinations.add(current);
return;
}
// 如果左括号数量小于 n，可以添加一个左括号
if (open < max) {
backtrack(current + "(", open + 1, close, max);
}
// 如果右括号数量小于左括号数量，可以添加一个右括号
if (close < open) {
backtrack(current + ")", open, close + 1, max);
}
}
}
当 n=2 时，我们来模拟一下整个题解过程。
①、开始：从一个空字符串开始，即当前字符串 current = ""，左括号数量 open = 0，
右括号数量 close = 0。
②、第一步：添加一个左括号。
• 可以添加左括号，因为 open < n。
• 不能添加右括号，因为 close = open。
• current = "("，open = 1，close = 0。
③、第二步：再添加一个左括号。
• current = "(("，open = 2，close = 0。
• 不能再添加左括号了，因为 open == n。
• 可以添加右括号，因为 close < open。
④、 第三步：添加一个右括号。
• current = "(()"，open = 2，close = 1。
• 不能再添加左括号，因为 open == n。
• 可以再添加一个右括号，因为 close < open。
⑤、第四步：添加最后一个右括号。
• current = "(())"，open = 2，close = 2。
• 到达一个有效的括号组合，记录这个组合。
⑥、回溯：回到第三步，探索其他可能性。我们回退一步，尝试在不同的位置添加右括
号。
• 将回溯到 "("，然后尝试先添加一个右括号变成 "()"，此时 open = 1，close = 1。
⑦、继续探索：在 "()" 的基础上，我们可以再添加一个左括号。
• current = "()("，open = 2，close = 1。
⑧、最后一步：添加最后一个右括号完成第二个有效组合。
• current = "()()"，open = 2，close = 2。
通过上述步骤，我们找到了所有可能的有效组合：
1. (())
2. ()()
来看一下题解效率：
022.%E6%8B%AC%E5%8F%B7%E7%94%9F%E6%88%90-20240203165636.png
总结
这道题我们仍然通过回溯方法来解决，使用 open 和 close 来跟踪左括号和右括号的数
量，当 open 和 close 都等于 n 时，我们就找到了一个有效的括号组合。
此时 return 回溯到上一步，继续探索其他可能性，此时回到上一级调用 backtrack("(()",
2, 1)，没有其他可能性了，我们再回溯到上一级调用 backtrack("((", 2, 0)，继续探索其
他可能性。
仍然没有，我们再回溯到上一级调用 backtrack("(", 1, 0)，继续探索其他可能性，此时
可以添加一个右括号，backtrack("()", 1, 1)，再添加一个左括号，backtrack("()(", 2,
1)，再添加一个右括号，backtrack("()()", 2, 2)，找到了一个有效的括号组合。
此时 return 回溯到上一级调用 backtrack("()(", 2, 1)，没有其他可能性了，我们再回溯到
上一级调用 backtrack("()", 1, 1)，继续探索其他可能性。
仍然没有。。。。
我把题解整理成了 ACM 模式，大家可以通过 debug 的模式感受一下整个题解过程。
class Main02201 {
public static void main(String[] args) {
Solution02201 solution = new Solution02201();
List<String> result = solution.generateParenthesis(2);
System.out.println(result);
}
}
class Solution02201 {
List<String> combinations = new ArrayList<>();
// 主方法，调用此函数生成所有的括号组合
public List<String> generateParenthesis(int n) {
backtrack("", 0, 0, n);
return combinations;
}
// 回溯方法
private void backtrack(String current, int open, int close, int max) {
// 如果当前字符串长度等于最大长度的两倍，说明找到了一个解，添加到结果列表中
if (current.length() == max * 2) {
combinations.add(current);
return;
}
// 如果左括号数量小于 n，可以添加一个左括号
if (open < max) {
backtrack(current + "(", open + 1, close, max);
}
// 如果右括号数量小于左括号数量，可以添加一个右括号
if (close < open) {
backtrack(current + ")", open, close + 1, max);
}
System.out.println("current: " + current + ", open: " + open + ", close: " +
close + ", max: " + max);
}
}
整个题解会尝试所有可能的括号组合，不断尝试，不断回溯。
022.%E6%8B%AC%E5%8F%B7%E7%94%9F%E6%88%90-20240203171734.png
大概就下面这个过程：
022.%E6%8B%AC%E5%8F%B7%E7%94%9F%E6%88%90-20240203172448.png
力扣链接：https://leetcode.cn/problems/generate-parentheses/