LeetCode LCR 085. 括号生成

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

题目描述

✅ LCR 085. 括号生成

题意分析

给定 n 对括号，要求生成所有由这 n 对括号组成的、能够正确闭合的字符串。答案的顺序不限，但必须不重不漏。

先把「有效」这个词说精确。一个只含 ( 和 ) 的串合法，当且仅当满足两条：任意前缀中 ( 的数量不少于 ) 的数量，且整串的 ( 与 ) 数量相等。前一条排除了 )( 这种「先关后开」，后一条排除了 (( 这种「开而不关」。这个刻画是全题的地基——它把一个看起来需要「事后校验」的性质，转化成了可以边生成边维护的增量条件。

题目要输出所有方案而不是方案数，说明必须真正把每个串构造出来。长度为 2n 的串共有 $2^{2n}$ 种填法，而合法的只有卡特兰数 $C_n$ 个（n = 8 时是 1430）。$2^{16} = 65536$ 对 1430，差了 40 多倍，说明先生成后过滤是可行但浪费的，而利用上面那两条前缀性质做剪枝可以让每一步都只走向有效状态。

约束 1 ≤ n ≤ 8 再次表明本题不考性能极限，而考枚举结构的设计。边界上：n = 1 时唯一答案是 "()"；答案里不会出现空串；由于每一步的选择序列各不相同，天然不会产生重复方案，因此不需要任何去重机制。

解法：动态规划递推

核心思路

暴力做法是把 2n 个位置各自填 ( 或 )，得到 $2^{2n}$ 个候选串，再逐个用「计数器扫一遍」验证合法性。瓶颈在于绝大多数候选在很靠前的位置就已经注定非法了——比如首字符填 )，后面 $2^{2n-1}$ 个串全部白算。

关键观察是：合法性的两条判据都只依赖已经填出的前缀，因此可以在生成过程中实时判断，一旦某个前缀不可能扩展成合法串就立刻停止。具体地，设当前前缀里已用了 left 个 (、right 个 )，那么下一步能填什么完全由这两个数决定：

能填 ( 当且仅当 left < n（左括号总数不能超过 n 对）；能填 ) 当且仅当 right < left（补上这个右括号后仍满足「前缀中左不少于右」）。这两个条件就是本解法的不变量：递归过程中任何时刻都有 right ≤ left ≤ n，即当前前缀始终是某个合法串的前缀。

因为不变量保证了「走到的每个状态都还有救」，搜索树上不存在死胡同：只要一路走到 left == right == n，得到的必然是一个合法串；反过来任何合法串也必然对应一条这样的路径。于是枚举与答案一一对应，不重不漏，且不需要任何合法性校验代码——非法状态压根不会被创建出来。

状态由 (left, right) 二元组完整刻画，路径上的字符串 t 只是把选择序列记录下来，不参与决策。

解题步骤

  • 确定递归状态：dfs(left, right, t) 中 left 是已用左括号数，right 是已用右括号数，t 是当前已拼出的前缀。只用这两个计数就够了，不需要额外记录「还差多少个未闭合」，因为它恰好等于 left - right。
  • 递归基：left == n && right == n 说明 2n 个字符全部填完且左右配平，直接把 t 收入答案并返回。这里不需要再做任何校验，正是因为不变量已经保证了合法性。
  • 尝试填左括号：if (left < n) 时递归 dfs(left + 1, right, t + "(")。条件是 left < n 而不是 left < 2n 之类——题目给的是 n 对括号，左右各 n 个。
  • 尝试填右括号：if (right < left) 时递归 dfs(left, right + 1, t + ")")。这一条是全题最关键的剪枝：必须是 right < left 而不是 right < n。用 right < n 会放行 ")(" 这类前缀，生成一堆非法串。
  • 不需要显式撤销：t + "(" 生成的是新字符串，当前栈帧里的 t 没有被修改，返回后自然还是原值。这是「传值路径」相对于「共享可变路径」的便利之处——代价是每层都产生一个新字符串对象。如果改用 StringBuilder 共享路径，就必须在递归后手动 deleteCharAt 撤销。

以 n = 2 走一遍，把状态记作 (left, right, t)。

根节点 (0, 0, "")。left = 0 < 2 可填左；right = 0 < left = 0 不成立，不能填右——首字符不可能是 )，这一步就砍掉了一半的候选。

进入 (1, 0, "(")。left = 1 < 2 可填左，进入 (2, 0, "((")；right = 0 < 1 也可填右，进入 (1, 1, "()")。

分支 (2, 0, "((")：left = 2 不小于 n，不能再填左；right = 0 < 2 可填右，进入 (2, 1, "(()")。该状态下 left 已满，right = 1 < 2 可填右，进入 (2, 2, "(())")，命中递归基，记下第一个答案 "(())"。

分支 (1, 1, "()")：left = 1 < 2 可填左，进入 (2, 1, "()(")；right = 1 < left = 1 不成立，不能填右——此处正是剪枝生效的地方，若允许会得到 "())" 这种前缀。继续从 (2, 1, "()(") 出发，left 已满，right = 1 < 2 可填右，进入 (2, 2, "()()")，记下第二个答案 "()()"。

最终答案为 ["(())", "()()"]，恰好是 $C_2 = 2$ 条，与卡特兰数吻合。若把 right < left 误写成 right < n，根节点就会先产出 ")" 开头的分支，n = 2 的输出会膨胀到 6 条，多出 ")("、"())(" 之类的非法串。

代码实现

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(n \times C_n)$，其中 $C_n = \binom{2n}{n} / (n+1)$ 是卡特兰数。由于剪枝保证每个被访问的状态都能扩展出至少一个答案，搜索树的叶子数恰为答案数 $C_n$，内部节点数与之同阶；每条答案在递归路径上累计做了 $O(n)$ 次字符串拼接。渐近上界可写作 $O(4^n / \sqrt{n})$。
  • 空间复杂度：$O(n)$，递归深度恰为 2n，每层持有一个长度不超过 2n 的字符串。若把每层新建的字符串都算上，栈上同时存活的字符总量是 $O(n^2)$，改用共享 StringBuilder 可降回 $O(n)$。返回值按惯例不计入。

关键点总结

  • 把「结果的合法性校验」改写成「过程中的增量约束」是这类构造题的核心手法：只要合法性可以由前缀判定，就能做到只生成有效状态、零校验、零去重。这个思路可以直接迁移到括号有效性、路径合法性一类问题上。
  • right < left 而不是 right < n，是本题唯一但致命的剪枝条件。面试中被问「为什么不能用 right < n」时，给出 ")(" 这个反例最直接。
  • 搜索路径本身就区分了不同答案，所以本题天生不需要去重。判断一道搜索题要不要去重，看的是「不同的选择序列会不会产出相同结果」，而不是凭感觉加 Set。
  • 传值路径与共享路径的取舍：t + "(" 写法简洁、无需撤销，代价是每层拷贝；StringBuilder 共享路径省内存，但必须成对写 append 与 deleteCharAt。面试时可以主动提出这个权衡。
  • 用卡特兰数自查：n = 1,2,3,4 的答案数分别是 1、2、5、14。写完随手对一下，多解或漏解立刻暴露。

易错点总结

  • 右括号的条件写成 right < n：n = 2 会输出 6 条，其中 ")("、")()(" 等根本不闭合。
  • 右括号的条件写成 right <= left：n = 1 时会在 (0,0,"") 处直接填 )，输出含 ")("。
  • 左括号的条件写成 left < 2 * n：n = 1 会尝试生成 "(("，左括号用超，最终既有非法串又永远凑不齐右括号。
  • 递归基只判 left == n：n = 2 时 "((" 一到齐就被当成答案收走，输出里混入长度只有 2 的残缺串。
  • 递归基判成 t.length() == 2 * n 却不检查配平：在没有 right < left 剪枝的前提下，n = 2 会把 "))((" 也收进答案。
  • 命中答案后忘记 return：left 与 right 都已达 n，两个 if 都不成立，虽然不会死循环，但多写的分支容易让人误加逻辑；若同时把条件放宽成 <=，就会无限递归直到栈溢出。
  • 改用 StringBuilder 共享路径却忘了 deleteCharAt 撤销：n = 2 时第一条答案 "(())" 之后，路径残留导致第二条被记成 "(())()(" 这类超长串。
  • 在 Go 里用 []byte 共享缓冲并 answer = append(answer, string(buf)) 之外还直接存 buf：切片共享底层数组，先存入的结果会被后续写入覆盖成乱码。
  • 先枚举 $2^{2n}$ 个串再用栈校验：n = 8 时要检查 65536 个候选而答案只有 1430 个，虽然勉强能过，但面试中会被追问「怎么避免生成非法串」，答不上就等于没解决题目真正考察的点。

相似题目

题目 难度 考察点
22. 括号生成 中等 与本题完全同题，代码可原样提交
面试题 08.09. 括号 中等 同题的另一处收录，返回值类型略有差异，可用来练手模板复用
20. 有效的括号 简单 只判定给定串是否合法，用栈匹配三种括号，是本题剪枝条件的判定版
301. 删除无效的括号 困难 反向操作：从非法串中删最少字符使其合法，需先算删除量再搜索并去重
32. 最长有效括号 困难 求最长合法子串长度，改用栈或线性 DP，不再枚举方案
1249. 移除无效的括号 中等 只需给出任意一个合法结果，两趟扫描标记待删位置即可，无须搜索
856. 括号的分数 中等 输入已保证合法，考察的是按嵌套层次计分的栈式解析