LeetCode 22. 括号生成
目录
题目描述
✅ 22. 括号生成
题意分析
给定括号对数
n，要求列出全部由n个'('和n个')'组成的有效括号串，顺序任意但不能重复、不能遗漏。这是一道枚举题，答案是一个集合而不是一个数值，所以正确性要同时论证「生成的都合法」和「合法的都生成」。先把「有效」这个词换成可以逐字符检查的条件。一个长度为
2n的括号串有效，等价于同时满足两条：左括号总数与右括号总数各为n；从左往右扫的过程中，任意前缀里右括号的数量都不超过左括号的数量。第二条是全题的支点——它不是对整个串的整体判断，而是对每个前缀都成立的局部判断，这意味着合法性可以在逐字符构造的过程中同步维护，不必等串写完再检验。数据范围只到
n不超过 8，答案个数是第n个卡特兰数（n = 8时是 1430），这个规模明确告诉我们：本题不指望多项式复杂度，指数级枚举是被接受的。因此考点不在压低量级，而在于枚举得既不重复也不遗漏，并且尽量不去走那些注定失败的分支。还有一个信号藏在「构造方式」里：串是从左到右一个字符一个字符长出来的，每一步只有两种选择。这种「位置固定、选项有限」的结构天然不会产生重复——两条不同的选择序列必然在某一位上字符不同，因此得到的字符串一定不同，答案里不需要额外去重。
需要留意的边界情形：
n = 1时唯一答案是["()"]；题目保证n至少为 1，所以不必处理n = 0；不要把「左括号用完」误当成「串已完成」，"(("这样左括号刚好用满n个的前缀离合法还差整整n个右括号。
解法：回溯生成合法前缀
核心思路
回溯时只生成合法前缀。左括号未用完就可以添加
'('；只有右括号数量小于左括号数量时，才能添加')'。路径长度达到2n时得到一个答案。
解题步骤
- 用
left、right记录已使用的左右括号数量。left < n时添加左括号，递归后撤销。right < left时添加右括号，递归后撤销。- 路径长度为
2n时保存当前字符串。
代码实现
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$ 个长度为
2n的合法串。- 空间复杂度：$O(n)$，递归栈和路径长度均为
2n；不计返回结果。
关键点总结
right < left保证任何前缀中右括号都不会多于左括号。- 两个分支必须分别判断，某些状态下需要同时尝试。
- 使用同一可变路径，并在递归返回后撤销最后一次选择。
易错点总结
- 把右括号条件写成
right < n，会生成非法前缀。- 左括号用完不等于字符串完成，终止条件应是长度达到
2n。- 忘记回溯撤销，会污染后续分支。
- Java 保存结果时要调用
path.toString()，不能保存可变对象本身。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 20. 有效的括号 | 简单 | 只判定单个串是否合法而不枚举，且有三种括号类型，需要用栈匹配而非两个计数器 |
| LCR 085. 括号生成 | 中等 | 与本题同题换号，可原样复用两份代码，适合用来检验是否真正记住了两个分支条件 |
| 面试题 08.09. 括号 | 中等 | 同为生成全部合法括号串，但题面额外强调结果不得重复，适合用来论证这个构造过程为何天然无重复 |