LeetCode LCR 085. 括号生成

约 4 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 动态规划 LCR 回溯

题目描述

✅ LCR 085. 括号生成

image-20260929010026034

题意分析

用 n 个左括号和 n 个右括号生成所有有效括号串。有效串必须满足：任意前缀中的左括号数不少于右括号数，最终两种括号都恰好使用 n 个。

如果一个前缀已经出现右括号比左括号多的情况，后面再补字符也无法改变这个错误前缀。因此可以从空串开始，只追加仍可能组成有效串的括号，避免先枚举全部字符串再验证。

解法：只扩展合法括号前缀

核心思路

[!blue]

left、right 分别表示当前前缀 t 中已使用的左、右括号数，始终保持 0 <= right <= left <= n。left-right 就是尚未闭合的左括号数，下一步只需按以下两个条件选择：

  • left < n 时还可以添加左括号，既不会超出数量上限，也不会破坏前缀合法性。
  • right < left 时才可以添加右括号，因为必须先有一个未闭合的左括号与它配对；仅检查 right < n 不足以保证这一点。

满足这些条件的前缀总能补成完整答案：先补足剩余左括号，再用剩余右括号逐一闭合即可。每次递归增加一个字符，因此最多深入 2n 层；当 left == right == n 时，所有前缀都合法且左右总数配平，直接收集 t。

任意合法答案的每一步都符合上述选择条件，所以不会被剪掉；两个不同的左右括号选择序列也不可能得到同一个字符串，所以无需额外去重。虽然计数决定了下一步的合法选择，不同前缀即使计数相同也不能合并，否则会漏掉不同答案。

当前代码用 t + "(" 或 t + ")" 创建新字符串，父层的 t 不会被修改，返回后无需显式撤销。两种选择可以同时合法，因此用两个独立的 if 分别展开。

解题步骤

  1. 从 dfs(0, 0, "") 开始，左右计数都为零。
  2. 两种括号都已用满时，将当前字符串加入答案并返回。
  3. 左括号还未用满时，追加左括号并递归。
  4. 仍有未闭合左括号时，追加右括号并递归。

代码实现

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

        dfs(0, 0, n, "", answer);

        return answer;
    }

    // left / right：已使用的左、右括号数量；t：当前前缀。
    private void dfs(int left, int right, int n, String t, List<String> answer) {
        if (left == n && right == n) {
            // 不变量保证走到这里的 t 一定合法，无需再校验。
            answer.add(t);

            return;
        }

        if (left < n) {
            dfs(left + 1, right, n, t + "(", answer);
        }

        // 必须是 right < left，写成 right < n 会放行 ")(" 这类非法前缀。
        if (right < left) {
            dfs(left, right + 1, n, t + ")", answer);
        }
    }
}

func generateParenthesis(n int) []string {
    var answer []string

    // left / right：已使用的左、右括号数量；t：当前前缀。
    var dfs func(left, right int, t string)
    dfs = func(left, right int, t string) {
        if left == n && right == n {
            // 不变量保证走到这里的 t 一定合法，无需再校验。
            answer = append(answer, t)
            return
        }
        if left < n {
            dfs(left+1, right, t+"(")
        }
        // 必须是 right < left，写成 right < n 会放行 ")(" 这类非法前缀。
        if right < left {
            dfs(left, right+1, t+")")
        }
    }

    dfs(0, 0, "")
    return answer
}

复杂度分析

  • 时间复杂度：$O(nC_n)$，C_n 为第 n 个卡特兰数：合法前缀搜索规模与 C_n 同阶，每次字符串拼接至多复制 O(n) 个字符。
  • 空间复杂度：当前各层保留独立前缀串，活跃字符总空间最坏 $O(n^2)$，递归帧为 $O(n)$，输出另占 $O(nC_n)$。

关键点总结

[!green]

  • 数量限制与前缀限制分别由 left < n、right < left 保证，最终才得到恰好 n 对括号。
  • 只生成合法前缀，完整结果不用再校验；不同选择序列对应不同答案，也不用集合去重。
  • 当前字符串不可变，递归拼接不会改变父层路径；各层仍会保留独立的前缀，空间不能只按递归帧数估算。

易错点总结

[!yellow]

  • 任何前缀都需右括号数不超过左括号数，右括号的条件是 right<left。
  • 左括号总数不能超过 n，只有两种括号都用满时才收集完整结果。
  • 当前字符串拼接写法无需回退共享路径；若换成可变缓冲区，则必须在回溯时撤销。

相似题目

题目 难度 关联与区别
20. 有效的括号 简单 原题验证给定括号串，本题构造时就维护左括号数不小于右括号数。
301. 删除无效的括号 困难 同样利用括号余额剪枝，原题从既有字符串中最少删除，本题从空串生成。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/49601822
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！