LeetCode 面试题 08.09. 括号

2026-03-28 HGNULB 约 8 分钟

文章信息 3 个分类 3 个标签

分类

题目描述

✅ 面试题 08.09. 括号

题意分析

给定正整数 n，要求列出所有由 n 对小括号组成的合法括号串。注意是「全部列举」而不是「计数」，返回值是 List<String>，所以答案规模本身就是指数级的，任何试图把它压到多项式时间的想法都不成立。

合法的定义可以拆成两条可在线判定的条件：从左往右扫描时，任意前缀里右括号数量都不能超过左括号数量；整串扫完时左右括号数量相等。这两条都是前缀性质——只要当前前缀已经违反，后面无论怎么补都救不回来。这个信号非常关键：它意味着可以边构造边判定，一旦不合法立刻掐断，而不必生成完整串再验证。

另一个信号来自约束里的「n 对」：串长固定为 $2n$，每个位置只有两种选择。这是一棵二叉的构造树，深度 $2n$，天然适合逐位决策的写法。

边界：n = 1 时唯一答案是 "()"；题目保证 n ≥ 1，不必处理 n = 0，但一个好的实现应该让 n = 0 自然返回只含空串的结果而不是崩溃。另外答案必须去重——但这里的构造方式按位置决策，天然不会产生重复串，不需要额外的 Set。

解法：动态规划递推

核心思路

最朴素的想法是枚举长度为 $2n$ 的全部 $2^{2n}$ 种字符串，再逐个检验合法性。瓶颈很直白：绝大多数串在很靠前的位置就已经废了，却仍被完整生成并检验一遍，做了大量无用功。

观察到合法性是前缀性质后，可以把「生成完再判」改成「边生成边判」：在填第 $k$ 位之前，前 $k-1$ 位是否合法已经确定，若不合法就整棵子树剪掉。

于是维护两个计数：l 表示当前串里已放的左括号数，r 表示已放的右括号数。当前串的内容完全由「按什么顺序放这些括号」决定，而是否还能继续往下走，只取决于 (l, r) 这一对数字。

显式写出这个搜索的不变量：进入 dfs(l, r, t) 时，t 是一个长度为 l + r 的串，它的每个前缀都满足「右括号数不超过左括号数」，且 t 中恰有 l 个左括号、r 个右括号。

维持不变量需要三个约束：l ≤ n（左括号不能超额）、r ≤ n（右括号不能超额）、l ≥ r（任意时刻右括号不能反超）。当 l == n && r == n 时，串长已达 $2n$ 且左右配平，t 就是一个完整答案。

这里的 l ≥ r 就是把「前缀合法」这个条件压缩成的一个数值不变量——它是整道题的核心，也是把指数级枚举削到卡特兰数量级的唯一原因。

解题步骤

把 n 提升为成员变量，答案列表也放在成员上。因为递归函数需要在每一层读 n 并往同一个列表里追加，避免在参数里反复传递。

递归函数签名取 dfs(l, r, t)，三个参数分别是已放左括号数、已放右括号数、当前串。之所以只需这三个量，是因为不变量已经说明「能否继续」只依赖 (l, r)，t 仅用于最终输出。

先做非法剪枝：l > n || r > n || l < r 时直接返回。三个条件缺一不可——前两个防止某一种括号超额，第三个防止右括号反超导致前缀非法。把剪枝写在函数入口而不是调用点，可以少写一半判断。

再做终止判断：l == n && r == n 时把 t 收进答案并返回。这一步必须排在剪枝之后，否则非法状态也可能被误收。

两个分支各放一个括号：dfs(l + 1, r, t + "(") 和 dfs(l, r + 1, t + ")")。因为每个位置只有这两种选择，穷举它们即可覆盖所有可能，而非法分支会在下一层入口被立刻掐掉。

无需手动回溯：这里用字符串拼接而非可变缓冲区，t + "(" 产生的是新对象，父层的 t 不受影响，所以不存在「用完要撤销」的问题。

以 n = 2 走一遍。根节点 dfs(0, 0, "")：合法，未完成，展开两个分支。

右分支 dfs(0, 1, ")") 一进入就撞上 l < r（0 < 1），直接返回——这正是剪枝在起作用，以 ) 开头的整棵子树被一次性砍掉。

左分支 dfs(1, 0, "(")：合法，继续展开。它的右分支 dfs(1, 1, "()") 合法但未满，再展开：其右分支 dfs(1, 2, "())") 撞上 l < r 返回；其左分支 dfs(2, 1, "()(") 合法，再往下左分支 dfs(3, 1, ...) 撞上 l > n 返回，右分支 dfs(2, 2, "()()") 命中终止条件，收入答案。

回到 dfs(1, 0, "(") 的左分支 dfs(2, 0, "((")：其左分支 dfs(3, 0, ...) 撞上 l > n 返回；右分支 dfs(2, 1, "(()") 合法，再往下右分支 dfs(2, 2, "(())") 命中终止条件，收入答案。

最终答案为 ["()()", "(())"]，与卡特兰数 $C_2 = 2$ 吻合。整棵树若不剪枝共有 $2^4 = 16$ 个叶子，实际只走到了 2 个。

代码实现

class Solution {
    private List<String> answer = new ArrayList<>();
    private int n;

    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(0, 0, "");
        return answer;
    }

    private void dfs(int l, int r, String t) {
        // l < r 表示右括号已经反超，该前缀无论怎么补都不可能合法。
        if (l > n || r > n || l < r) {
            return;
        }
        if (l == n && r == n) {
            answer.add(t);
            return;
        }
        dfs(l + 1, r, t + "(");
        dfs(l, r + 1, t + ")");
    }
}

func generateParenthesis(n int) []string {
    answer := []string{}
    var dfs func(int, int, string)
    dfs = func(l, r int, t string) {
        // l < r 表示右括号已经反超，该前缀无论怎么补都不可能合法。
        if l > n || r > n || l < r {
            return
        }
        if l == n && r == n {
            answer = append(answer, t)
            return
        }
        dfs(l+1, r, t+"(")
        dfs(l, r+1, t+")")
    }
    dfs(0, 0, "")
    return answer
}

复杂度分析

时间复杂度：$O(\frac{4^n}{\sqrt{n}})$。合法括号串的个数是第 n 个卡特兰数 $C_n = \frac{1}{n+1}\binom{2n}{n}$，渐近于 $\frac{4^n}{n\sqrt{\pi n}}$；每个答案需要 $O(n)$ 的字符串拼接与写入，两者相乘即为上式。剪枝保证被访问的节点数与答案数同阶，不存在白跑的整棵子树。

空间复杂度：$O(n)$（不计返回值）。递归深度最深为 $2n$，每层持有一个长度不超过 $2n$ 的串；由于字符串拼接会在每层复制，栈上总字符量是 $O(n^2)$ 级，但按「辅助空间随 n 线性增长的层数」计通常记作 $O(n)$，若严格计入拷贝则为 $O(n^2)$。

关键点总结

把「合法」翻译成可在线判定的数值不变量是这类构造题的通用套路：这里 l ≥ r 和 l, r ≤ n 三条就完整刻画了合法前缀，剩下的只是机械穷举。

剪枝写在递归入口，而不是每个调用点，代码量减半且不会漏判；代价是多一次函数调用开销，白板上这个取舍几乎总是选前者。

答案规模决定复杂度下界：面试时先说清「输出本身就是卡特兰数量级」，再说自己的算法没有额外浪费，比直接背一个复杂度公式更有说服力。

按位置决策天然去重：每个合法串对应唯一一条根到叶的路径，不需要 Set。面试官若追问「会不会重复」，这就是标准答案。

字符串拼接 vs StringBuilder：拼接写法省掉了显式回溯，逻辑更短更不易错；若面试官关心常数，可以补一句「改成 StringBuilder + 尾部删除可以把每层拷贝降为 $O(1)$」。

这道题和 22. 括号生成完全同题，回答时可以直接指出来，并顺势提一句「计数版本就是卡特兰数，可以用 $O(n)$ 递推」，展示对题族的整体认知。

易错点总结

剪枝条件漏写 l < r：n = 1 时会生成 ")(" 这种右括号反超的串，答案里混入非法结果。

剪枝条件漏写 l > n 或 r > n：递归不会在深度 $2n$ 处停下，n = 2 时会一路往下走到 l = 3, 4, 5…，最终栈溢出。

把终止判断写在剪枝之前：先判 l == n && r == n 再判 l < r 时，虽然 l == n && r == n 本身蕴含 l == r，但如果把终止条件误写成 l + r == 2 * n，n = 2 下的 "()))" 类状态就会被当成答案收走。

终止条件写成 t.length() == 2 * n 却不检查配平：在没有 l < r 剪枝兜底的实现里，n = 2 会收进 "(())" 之外的非法长串。

两个分支的计数加错：写成 dfs(l + 1, r, t + ")")，n = 1 时输出 ")" 开头的串，l/r 的语义与实际字符不再对应。

用 StringBuilder 却忘记回溯：sb.append('(') 递归后不执行 sb.deleteCharAt(sb.length() - 1)，n = 2 时第二个分支会在 "((" 的基础上继续追加，得到 "((()" 之类的垃圾。

answer 声明为局部变量却在递归中重新赋值：Java 里在 dfs 内 answer = new ArrayList<>() 会让上层引用失效，最终返回空列表。

Go 中把 answer 通过值参数传入递归：append 扩容后新切片只在本层可见，n = 3 时会丢结果；必须用闭包捕获或返回值回传。

n = 1 时返回空列表：通常是把终止条件写成 l == n && r == n && l + r > 0 之类的多余限制，或是把递归入口误写成 dfs(1, 0, "(") 却没相应调整边界。

忘记 dfs 命中终止条件后 return：会继续往下展开两个分支，虽然子调用会被 l > n 剪掉不产生错误答案，但白白多跑两层调用，n 较大时常数明显变差。

相似题目

题目	难度	考察点
22. 括号生成	中等	与本题完全同题，可直接套用同一份 `dfs`
LCR 085. 括号生成	中等	同题的 LCR 版本，仅函数名不同
20. 有效的括号	简单	反向问题：判定而非构造，且含三种括号，需要用栈匹配类型
32. 最长有效括号	困难	求最长合法子串长度，栈存下标或 dp 记录以 `i` 结尾的最长合法长度
678. 有效的括号字符串	中等	引入通配符 `*`，把单一计数换成左括号数的可行区间 `[lo, hi]`
301. 删除无效的括号	困难	先算出最少删除数再搜索，重点是同层相同字符的去重剪枝
1249. 移除无效的括号	中等	只求任意一个合法解，两次线性扫描标记待删下标即可，无需搜索
856. 括号的分数	中等	在合法串上做求值，栈里存的是分数而不是括号本身
1614. 括号的最大嵌套深度	简单	只需记录扫描过程中计数器的最大值，是本题不变量的最简用法