回溯中等1 种解法
#22括号生成
在任意前缀都合法的约束下，生成 n 对括号的全部组合。
#回溯#字符串#剪枝
原题
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
解题主线
- 只有已使用的右括号少于左括号时，才能继续放右括号。
- 把非法前缀提前剪掉后，搜索树只保留合法括号序列的前缀。
解法 1：合法前缀回溯
记录已经放置的左右括号数：左括号未满时可放左括号，close < open 时才可放右括号。
-
时间复杂度： O(Cn × n)，Cn 为第 n 个卡特兰数，复制每个结果需要 O(n)
-
空间复杂度： O(n)，不计输出
import java.util.ArrayList;
import java.util.List;
final class Solution {
public List<String> generateParenthesis(int n) {
if (n < 0) {
throw new IllegalArgumentException("n must be non-negative");
}
List<String> result = new ArrayList<>();
backtrack(n, 0, 0, new StringBuilder(2 * n), result);
return result;
}
private void backtrack(int n, int open, int close, StringBuilder path, List<String> result) {
// 长度达到 2n 时，合法前缀不变量保证当前路径就是完整答案。
if (path.length() == 2 * n) {
result.add(path.toString());
return;
}
// 左括号总数不能超过 n。
if (open < n) {
path.append('(');
backtrack(n, open + 1, close, path, result);
// 共享路径在返回父层前必须恢复。
path.deleteCharAt(path.length() - 1);
}
// 仅当已有未匹配左括号时才能添加右括号，剪掉非法前缀。
if (close < open) {
path.append(')');
backtrack(n, open, close + 1, path, result);
path.deleteCharAt(path.length() - 1);
}
}
}边界与易错点
- 若用“剩余数量”建模，必须保证剩余左括号不多于剩余右括号；若用“已使用数量”建模，则条件方向相反。
- 字符串拼接写法无需显式撤销，但会产生更多临时对象；共享 StringBuilder 时必须成对撤销。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
backtrack/Q022_traverse_generateParenthesis.java