#22
中等
中频
回溯括号生成
这是一道围绕算法展开的高频练习。建议先掌握「回溯」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
算法
题目分析
这道题表面上是在处理「括号生成」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考 算法 这些能力。这类题更像在一棵决策树里向下展开，关键是递归时带什么状态、什么时候回退。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：回溯构造括号串，左括号数量没用完就能继续放，右括号数量必须严格小于左括号已放数量时才能放。
推荐代码
推荐解法：回溯
时间复杂度： O(Cn)
空间复杂度： O(n)
核心思路： 回溯构造括号串，左括号数量没用完就能继续放，右括号数量必须严格小于左括号已放数量时才能放。
class Solution {
/**
* 回溯法生成括号
* 时间复杂度: O(4^n / sqrt(n))
* 空间复杂度: O(4^n / sqrt(n))
*/
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<String>();
backtrack(ans, new StringBuilder(), 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
if (cur.length() == max * 2) {
ans.add(cur.toString());
return;
}
if (open < max) {
cur.append('(');
backtrack(ans, cur, open + 1, close, max);
cur.deleteCharAt(cur.length() - 1);
}
if (close < open) {
cur.append(')');
backtrack(ans, cur, open, close + 1, max);
cur.deleteCharAt(cur.length() - 1);
}
}
}结构化讲解
面试时怎么讲
开场思路
这题我会用回溯，但关键在于只扩展合法前缀。
核心过程
- 递归中记录当前已放的左括号数和右括号数。
- 左括号只要没用完就可以继续放。
- 右括号只有在当前左括号更多时才能放。
- 当字符串长度达到
2n时，当前路径就是一个合法答案。
复杂度总结
时间复杂度和卡特兰数同阶，空间复杂度 O(n)。
面试补一句：这题最核心的不变量是“任何前缀中右括号数量不能超过左括号”。
核心思路
括号生成的核心不是枚举所有 2^(2n) 个串再筛，而是只在构造过程中维护合法前缀。这样非法分支会被提前剪掉。
步骤讲解
1
维护左右括号已使用数量
递归时记录已经放了多少个左括号和右括号。
为什么这样做：后续能否继续放某种括号，全靠这两个计数判断。
对应代码提示：dfs(open, close, path);
2
左括号没用完时可以继续放
只要左括号数量还小于 n，就能在当前前缀后加一个 (。
为什么这样做：左括号本身不会立即破坏合法性，可以放心扩展。
对应代码提示：if (open < n) dfs(open + 1, close, path + "(");
3
右括号只有在不破坏前缀合法时才能放
当 close < open 时才能添加 )，保证任何前缀里都不会右括号多于左括号。
为什么这样做：合法括号串的关键约束就是所有前缀都必须可匹配。
对应代码提示：if (close < open) dfs(open, close + 1, path + ")");
易错点
先生成所有字符串再过滤
分支数爆炸，而且大部分字符串一开始就是非法的。
正确理解：直接在回溯过程中维护合法前缀约束。
只限制总数，不限制前缀合法性
会生成很多像 )( 这样的非法中间状态。
正确理解：始终保证
close <= open。结果长度到 2n 后没立即收集
继续递归没有意义，还可能造成重复结果。
正确理解：长度达到
2*n 时直接加入答案并返回。复杂度与适用判断
时间复杂度：O(Cn)
空间复杂度：O(n)
比其他方案更好在哪里：比暴力枚举后筛选高效得多，剪枝发生在搜索过程而不是结果阶段。
适用判断：构造类题只要要求所有前缀都满足约束，优先考虑回溯 + 合法前缀剪枝。
额外提醒
- 合法括号串的关键约束发生在前缀，而不只是最终总数。
其他语言 / 其他解法
暴力解法
生成所有可能的2^(2n)个括号组合，然后验证每个组合以找到有效的组合。
暴力解法
生成所有可能的2^(2n)个括号组合，然后验证每个组合以找到有效的组合。
时间复杂度：O(2^(2n) * n)
空间复杂度：O(2^(2n) * n)
一句话思路：生成所有可能的2^(2n)个括号组合，然后验证每个组合以找到有效的组合。
class Solution {
/**
* 暴力法生成括号
* 时间复杂度: O(2^(2n) * n)
* 空间复杂度: O(2^(2n) * n)
*/
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList<String>();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current)) {
result.add(new String(current));
}
} else {
current[pos] = '(';
generateAll(current, pos + 1, result);
current[pos] = ')';
generateAll(current, pos + 1, result);
}
}
public boolean valid(char[] current) {
int balance = 0;
for (char c: current) {
if (c == '(') {
++balance;
} else {
--balance;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
}动画演示
如果你还没完全看懂，可以展开动画演示。
回溯动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
回溯动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入n值，然后点击开始
暴力解法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
暴力解法动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入n值，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。