力扣热题100实战 | 第22期：括号生成——回溯算法的进阶应用

力扣热题100实战 | 第22期：括号生成——回溯算法的进阶应用

• • 前言
  • 一、题目：生成所有有效的括号组合
  • • 关键点解读
  • 二、第一反应：暴力枚举（超时但思路正确）
  • • 核心思想
    • 代码实现
    • 复杂度分析
    • 这段代码的问题在哪？
  • 三、核心解法：回溯算法 + 剪枝（面试标准答案）
  • • 为什么需要剪枝？
    • 两个关键的剪枝条件
    • 算法步骤
    • 图解流程
    • 代码实现（String版，推荐）
    • 代码实现（StringBuilder版，更高效）
    • 代码解析
    • 复杂度分析
  • 四、两种剪枝条件的深度对比
  • 五、细节剖析：面试官真正关心的问题
  • • Q1：为什么用剩余数量 `left` 和 `right`，而不是已使用数量？
    • Q2：剪枝条件 `right > left` 是怎么推导出来的？
    • Q3：String 版和 StringBuilder 版哪个更好？
    • Q4：为什么不用 StringBuffer？
    • Q5：n=0 时为什么返回 `[""]` 而不是空列表？
  • 六、面试官追问进阶版
  • • 追问1：如何用动态规划实现括号生成？
    • 追问2：如何输出所有括号组合的长度？
    • 追问3：如何验证一个括号字符串是否有效（不用栈）？
    • 追问4：如果要求生成所有可能的括号组合（包括无效的），怎么改？
  • 七、实际开发：这道题到底有什么用？
  • • 场景1：编译器语法检查
    • 场景2：数据库查询优化
    • 场景3：二叉树遍历的序列化
    • 场景4：数学表达式求值
    • 场景5：正则表达式匹配
  • 八、总结：从一道题到一类题
  • 附录：思考题

如果说电话号码的字母组合是回溯算法的入门，那么括号生成就是回溯算法的进阶——它不仅需要枚举所有可能，还要在枚举过程中动态维护合法性。这种“边构建边验证”的思想，正是回溯算法的精髓所在。

前言

你好，我是@礼拜天没时间。

上一期我们学习了合并两个有序链表，掌握了链表操作的基础技巧。这一期，我们回到回溯算法专题，来解一道比“电话号码的字母组合”更进一阶的题目——括号生成（LeetCode 第22题）。

这道题在力扣上被标记为“中等”，但它的难度其实不在于代码的复杂度，而在于如何在递归过程中维护括号的有效性。很多同学第一次接触这道题时，要么生成的括号数量不对，要么生成了无效的括号序列，要么代码写得冗长复杂。

今天，我希望能带你从暴力枚举的思路出发，一步步推导出带有剪枝的回溯解法，并理解回溯算法中“剪枝”这个核心概念。

一、题目：生成所有有效的括号组合

先看题目描述（LeetCode 第22题）：

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

示例 1：

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

示例 2：

输入：n = 1
输出：["()"]

示例 3：

输入：n = 0
输出：[""]

关键点解读

二、第一反应：暴力枚举（超时但思路正确）

当我第一次看到这道题，我的第一反应是：生成所有可能的括号序列，然后筛选出有效的 。

核心思想

代码实现

class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
if (n == 0) {
result.add("");
return result;
}

// 生成所有可能的序列
generateAll(new char[2 * n], 0, result);
return result;
}

private void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
// 检查是否有效
if (isValid(current)) {
result.add(new String(current));
}
return;
}

// 尝试放左括号
current[pos] = '(';
generateAll(current, pos + 1, result);

// 尝试放右括号
current[pos] = ')';
generateAll(current, pos + 1, result);
}

private boolean isValid(char[] current) {
int balance = 0;
for (char c : current) {
if (c == '(') {
balance++;
} else {
balance—;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
}

复杂度分析

• 时间复杂度：O(2^(2n) × n) —— 需要生成 2^(2n) 种组合，每种组合需要 O(n) 时间检查有效性
• 空间复杂度：O(2n) —— 递归栈深度和字符数组的空间

这段代码的问题在哪？

三、核心解法：回溯算法 + 剪枝（面试标准答案）

为什么需要剪枝？

在生成括号的过程中，我们可以利用有效括号的性质，提前终止那些不可能形成有效解的递归分支 。

两个关键的剪枝条件

算法步骤

图解流程

以 n = 3 为例，递归树如下（括号内表示剩余的左右括号数） ：

root (3,3)
/ \\
(2,3) ×(不能放右括号)
/ \\
(1,3) (2,2)
/ \\ / \\
(0,3) (1,2) (1,2) (2,1)
| / \\ / \\ |
… … … … …

通过剪枝，我们只探索那些可能形成有效解的分支，大大减少了搜索空间。

代码实现（String版，推荐）

class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
if (n == 0) {
result.add("");
return result;
}

backtrack(result, "", n, n);
return result;
}

/**
* 回溯生成括号组合
* @param result 结果集
* @param current 当前构建的字符串
* @param left 剩余可用的左括号数量
* @param right 剩余可用的右括号数量
*/
private void backtrack(List<String> result, String current, int left, int right) {
// 终止条件：所有括号都用完了
if (left == 0 && right == 0) {
result.add(current);
return;
}

// 剪枝条件1：剩余左括号大于0，可以放左括号
if (left > 0) {
backtrack(result, current + "(", left – 1, right);
}

// 剪枝条件2：剩余右括号大于剩余左括号，才能放右括号
// 因为当前序列中已有的左括号数 = n – left，已有的右括号数 = n – right
// 需要保证已有的右括号数 < 已有的左括号数，即 n – right < n – left => left < right
// 所以 right > left 是放右括号的必要条件
if (right > left) {
backtrack(result, current + ")", left, right – 1);
}
}
}

代码实现（StringBuilder版，更高效）

class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
if (n == 0) {
result.add("");
return result;
}

backtrack(result, new StringBuilder(), n, n);
return result;
}

private void backtrack(List<String> result, StringBuilder current, int left, int right) {
if (left == 0 && right == 0) {
result.add(current.toString());
return;
}

if (left > 0) {
current.append('(');
backtrack(result, current, left – 1, right);
current.deleteCharAt(current.length() – 1); // 回溯撤销
}

if (right > left) {
current.append(')');
backtrack(result, current, left, right – 1);
current.deleteCharAt(current.length() – 1); // 回溯撤销
}
}
}

代码解析

复杂度分析

• 时间复杂度：O(4^n / √n)，这是第 n 个卡特兰数的渐近复杂度
• 空间复杂度：O(n)，递归栈的深度最大为 2n

四、两种剪枝条件的深度对比

为了帮助读者更好地理解，我将两个剪枝条件的作用和意义总结如下：

这两个条件共同作用，确保我们只生成有效的括号组合 。

五、细节剖析：面试官真正关心的问题

Q1：为什么用剩余数量 left 和 right，而不是已使用数量？

答案：两种方式都可以，但用剩余数量更直观地体现“可用资源”的概念 。当 left == 0 && right == 0 时，所有资源耗尽，得到一个解。如果用已使用数量，终止条件是 usedLeft == n && usedRight == n。

Q2：剪枝条件 right > left 是怎么推导出来的？

答案：假设当前剩余左括号为 left，剩余右括号为 right，那么已经使用的左括号数为 n – left，已经使用的右括号数为 n – right。为了保证序列合法，必须有 n – right < n – left，即 left < right，也就是 right > left 。

Q3：String 版和 StringBuilder 版哪个更好？

答案 ：

• String版：代码简洁，不易出错，适合面试快速写出
• StringBuilder版：性能更好（减少对象创建），但需要手动回溯，容易忘记 deleteCharAt
• 建议：面试中用 String 版即可，如果时间充裕可以补充说明优化方案

Q4：为什么不用 StringBuffer？

答案：StringBuffer 是线程安全的，有同步开销，在单线程场景下不如 StringBuilder 高效。本题是单线程算法，用 StringBuilder 即可。

Q5：n=0 时为什么返回 [""] 而不是空列表？

答案：按照题目要求，n=0 表示生成0对括号，唯一的组合是空字符串。这符合卡特兰数的定义：C(0) = 1 。

六、面试官追问进阶版

追问1：如何用动态规划实现括号生成？

思路 ：动态规划解法基于一个巧妙的递推关系。

f(n) 可以表示为 "(" + f(i) + ")" + f(n-1-i)，其中 i 从 0 到 n-1。

public List<String> generateParenthesis(int n) {
List<List<String>> dp = new ArrayList<>();
dp.add(Collections.singletonList(""));

for (int i = 1; i <= n; i++) {
List<String> cur = new ArrayList<>();
for (int j = 0; j < i; j++) {
for (String left : dp.get(j)) {
for (String right : dp.get(i – 1 – j)) {
cur.add("(" + left + ")" + right);
}
}
}
dp.add(cur);
}

return dp.get(n);
}

复杂度：同样是卡特兰数，但空间复杂度 O(n × Catalan) 较高。

追问2：如何输出所有括号组合的长度？

思路：直接返回卡特兰数公式的结果。

public int countParenthesis(int n) {
// 卡特兰数公式：C(2n, n) / (n + 1)
return combination(2 * n, n) / (n + 1);
}

private int combination(int n, int k) {
long res = 1;
for (int i = 1; i <= k; i++) {
res = res * (n – k + i) / i;
}
return (int) res;
}

追问3：如何验证一个括号字符串是否有效（不用栈）？

思路：用计数器即可，左括号加1，右括号减1，过程中不能为负，最终为0 。

public boolean isValid(String s) {
int count = 0;
for (char c : s.toCharArray()) {
if (c == '(') count++;
else count—;
if (count < 0) return false;
}
return count == 0;
}

追问4：如果要求生成所有可能的括号组合（包括无效的），怎么改？

思路：去掉剪枝条件，只限制长度，然后过滤。

public List<String> generateAll(int n) {
List<String> result = new ArrayList<>();
generateAllHelper(new char[2 * n], 0, result);
return result;
}

private void generateAllHelper(char[] current, int pos, List<String> result) {
if (pos == current.length) {
result.add(new String(current));
return;
}
current[pos] = '(';
generateAllHelper(current, pos + 1, result);
current[pos] = ')';
generateAllHelper(current, pos + 1, result);
}

七、实际开发：这道题到底有什么用？

很多读者会问：“括号生成，实际工作中哪用得到？”

其实它的思想无处不在：

场景1：编译器语法检查

编译器的语法分析阶段，需要检查代码中的括号是否匹配。理解括号生成的原理，有助于理解编译器的工作原理 。

场景2：数据库查询优化

某些数据库查询优化算法中，需要枚举不同的执行计划组合，这与括号生成的思想类似。

场景3：二叉树遍历的序列化

二叉树的序列化表示（如用括号表示子树）与括号生成有异曲同工之妙。

场景4：数学表达式求值

在数学表达式求值中，括号的嵌套关系决定了运算顺序，理解括号生成有助于设计表达式解析器。

场景5：正则表达式匹配

正则表达式中的 *、+ 等量词，与括号的生成规则有相似之处，都是递归定义的。

八、总结：从一道题到一类题

回顾一下，我们从括号生成学到了什么：

力扣热题100的第二十二题，不是为了难住你，而是为了告诉你：回溯算法的精髓不在于“尝试所有可能”，而在于“优雅地排除不可能”。当你掌握了剪枝的艺术，你就能在指数级的搜索空间中找到那条通往答案的捷径。

下一期预告：《合并K个升序链表》——优先队列的经典应用

附录：思考题

看完这篇文章，你可以试着回答：

欢迎在评论区留下你的思考！