LeetCode 面试题 08.09. 括号

约 4 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
字符串 动态规划 回溯

题目描述

✅ 面试题 08.09. 括号

image-20260929011215221

题意分析

生成恰好 n 对括号的全部合法字符串，结果不能重复。合法不仅要求左右括号总数相同，还要求从左向右读到任何位置时，右括号都不能比左括号多，因为每个右括号都要匹配此前出现的左括号。

解法：只扩展可能合法的括号前缀

核心思路

[!blue]

定义 dfs(l, r, t)：已经放入 l 个左括号、r 个右括号，形成前缀 t。每步只追加一种括号，并增加对应计数，最终分别用完 n 个左右括号。

若 l > n 或 r > n，数量已经超出要求；若 r > l，当前前缀已经出现没有左括号可匹配的右括号。后续只能在末尾追加，无法在这个右括号之前补入左括号，所以这三种情况都可以立即剪枝。

当 l == n && r == n 时，总数量已满，而且之前每个前缀都通过了检查，因此当前串合法，可以直接加入答案。其他合法前缀继续尝试追加左括号和右括号；代码由下一次递归入口统一排除不合法的尝试。

任意合法完整串的所有前缀都满足这些限制，所以它对应的逐字符选择不会被剪掉；不同选择路径又必然在某一位字符不同，因此结果不重不漏。字符串拼接产生新值，父层的 t 不会被子层改动，不需要手动删除末尾字符。

解题步骤

  1. 从 dfs(0, 0, "") 开始。
  2. 进入递归时先检查数量是否超过 n，以及右括号是否多于左括号，不满足就返回。
  3. 左右括号都已用完时，保存当前字符串并返回。
  4. 分别递归到追加左括号和追加右括号的状态。
  5. 所有可行前缀搜索结束后返回答案。若 n = 0，空字符串本身就是唯一完整结果。

代码实现

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
}

复杂度分析

  • 时间复杂度：设合法结果数为第 $n$ 个卡特兰数 $C_n$，输出本身需要 $\Theta(nC_n)$ 个字符。每个合法前缀都属于至少一个结果，按每个结果至多 $2n$ 个前缀计，搜索节点数有 $O(nC_n)$ 上界；当前每次字符串拼接还需复制至多 $O(n)$ 个字符，因此可给出包含复制成本的保守上界 $O(n^2C_n)$。
  • 空间复杂度：不计输出时为 $O(n^2)$。递归深度是 $O(n)$，但路径上的不同层同时持有逐渐变长的字符串，长度之和为平方级；输出另外占 $O(nC_n)$。

关键点总结

[!green]

  • 数量不超限和每个前缀右括号不反超，共同保证完整结果合法。
  • 非法前缀无法靠后缀修复，剪枝只删除不可能产生答案的分支。
  • 代码使用不可变字符串传递状态，无需撤销，但要计入拼接的复制成本。

易错点总结

[!yellow]

  • 只在最后检查左右总数相同，会接受中途已经无法匹配的前缀。
  • 不能只限制总长度，左右两类括号各自都不能超过 n。
  • 当前实现是带剪枝的回溯，计数状态并不意味着使用了动态规划或记忆化。
  • 不能仅按递归层数将辅助空间记成 $O(n)$，各层字符串也同时占用空间。

相似题目

题目 难度 关联与区别
20. 有效的括号 简单 原题验证一个给定括号串，本题在构造阶段就维护单种括号的合法前缀条件。
301. 删除无效的括号 困难 同样利用左右括号余额排除非法前缀，原题还要在给定字符串上最少删除。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/41089608
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！