LeetCode 22. 括号生成

2026-09-07 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 中等已解决需复习 100-200 LeetCode 热题 100 面试经典 150 题腾讯字节阿里华为微软美团拼多多京东小米百度网易小红书快手滴滴 B站虾皮商汤猿辅导作业帮

题目描述

✅ 22. 括号生成

题意分析

用 n 个左括号和 n 个右括号，生成所有有效的括号字符串，每个结果的长度都是 2n。需要返回不同的字符串本身，而不是只返回方案数量。

有效括号不仅要求左右括号总数相同，还要求从左向右读取的任意前缀中，右括号数都不能超过左括号数：每个右括号都必须能匹配它前面尚未配对的左括号。两项条件同时成立，整个字符串才有效。

解法：回溯生成合法前缀

核心思路

[!blue]

从空字符串开始，逐位决定放左括号还是右括号。若先生成所有长度为 2n 的括号串再判断是否合法，会探索大量已经不可能成为答案的前缀。回溯时直接限制每一步的选择，可以让路径始终合法。

用 path 保存当前前缀，left、right 分别表示已经使用的左右括号数量。保持 0 <= right <= left <= n：left < n 时还可以放一个左括号；right < left 时，前面还有未配对的左括号，才可以放一个右括号。若右括号已经比左括号多，后面再补左括号也无法修复此前的非法前缀，因此这样的分支根本不用进入。

两个条件可能同时成立，这时两种选择都要探索，因此使用两个独立的 if。每次添加一个字符后递归，返回时删除刚加入的字符，使 path 恢复到选择之前的状态；后一个分支才能从同一个前缀出发。left、right 是按值传递的，不需要手动撤销。

当 path 长度达到 2n 时，结合 right <= left <= n，必然有 left = right = n，而每个前缀也都合法，所以可以直接保存答案。反过来，任何有效串的每一步都会满足上述选择条件，回溯一定能够走到它；不同选择序列得到不同字符串，因此既不会遗漏，也无需额外去重。

解题步骤

创建空路径和结果列表，从 left = 0、right = 0 开始回溯。

每次进入递归，若路径长度为 2n，将路径转成字符串保存，然后返回。

若 left < n，添加左括号，以 left + 1 递归；返回后删除最后一个字符。

独立判断 right < left。若成立，添加右括号，以 right + 1 递归；返回后同样撤销该字符。

代码实现

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

        backtrack(n, 0, 0, new StringBuilder(), result);

        return result;
    }

    private void backtrack(int n, int left, int right, StringBuilder path, List<String> result) {
        if (path.length() == 2 * n) {
            result.add(path.toString());

            return;
        }

        // 左括号只受总数量限制，这个分支与右括号分支分别判断。
        if (left < n) {
            path.append('(');
            backtrack(n, left + 1, right, path, result);
            path.deleteCharAt(path.length() - 1);
        }

        // 右括号不能超过已用左括号；两种选择独立尝试，递归后各自撤销。
        if (right < left) {
            path.append(')');
            backtrack(n, left, right + 1, path, result);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

func generateParenthesis(n int) []string {
    result := make([]string, 0)
    path := make([]byte, 0, 2*n)

    var backtrack func(int, int)
    backtrack = func(left, right int) {
        if len(path) == 2*n {
            result = append(result, string(path))
            return
        }

        // 左括号只受总数量限制，这个分支与右括号分支分别判断。
        if left < n {
            path = append(path, '(')
            backtrack(left+1, right)
            path = path[:len(path)-1]
        }
        // 右括号不能超过已用左括号；两种选择独立尝试，递归后各自撤销。
        if right < left {
            path = append(path, ')')
            backtrack(left, right+1)
            path = path[:len(path)-1]
        }
    }

    backtrack(0, 0)
    return result
}

复杂度分析

时间复杂度：$O(nC_n)=O(4^n/\sqrt{n})$，其中 $C_n=\frac{1}{n+1}\binom{2n}{n}$ 是 n 对括号的有效字符串数量，即第 n 个卡特兰数。每个答案长 2n，转成字符串并保存需要 $O(n)$ 时间；遍历合法前缀的开销也包含在该上界中。

空间复杂度：$O(n)$，不计返回结果。递归深度和路径长度最多为 2n；保存全部答案另需 $O(nC_n)$ 空间。

关键点总结

[!green]

有效性由每个前缀的配对条件保证，数量限制由 left <= n 保证，终点不必再次扫描判断。

回溯不是遇到一个合法选择就结束，而是分别探索当前前缀下所有合法选择。

Java 的 StringBuilder 和 Go 的字节切片复用同一路径；保存结果时转成独立字符串，回溯时恢复路径。

易错点总结

[!yellow]

只用 right < n 限制右括号，会允许右括号出现在没有可匹配左括号的位置；应使用 right < left。

两个分支写成 if/else，会在还能放左括号时跳过合法的右括号选择，导致漏解。

左括号用完不等于整个字符串完成，剩余右括号仍需补齐；终止条件是长度达到 2n。

添加字符后必须在递归返回时删除该字符，否则其他分支会继承不属于自己的选择。

相似题目

题目	难度	关联与区别
20. 有效的括号	简单	原题验证给定括号串，本题构造时就维护左括号数不小于右括号数。
301. 删除无效的括号	困难	同样利用括号余额剪枝，原题从既有字符串中最少删除，本题从空串生成。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/55185444

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！