回溯中等1 种解法

#22括号生成

在任意前缀都合法的约束下，生成 n 对括号的全部组合。

#回溯#字符串#剪枝

解题主线

只有已使用的右括号少于左括号时，才能继续放右括号。

把非法前缀提前剪掉后，搜索树只保留合法括号序列的前缀。

解法 1：合法前缀回溯

记录已经放置的左右括号数：左括号未满时可放左括号，close < open 时才可放右括号。

时间复杂度

O(Cn × n)，Cn 为第 n 个卡特兰数，复制每个结果需要 O(n)

空间复杂度

O(n)，不计输出

22. 括号生成 · 合法前缀回溯

java

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) {
        if (path.length() == 2 * n) {
            result.add(path.toString());
            return;
        }
        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);
        }
    }
}

记录已经放置的左右括号数：左括号未满时可放左括号，close < open 时才可放右括号。

边界与易错点

若用“剩余数量”建模，必须保证剩余左括号不多于剩余右括号；若用“已使用数量”建模，则条件方向相反。
字符串拼接写法无需显式撤销，但会产生更多临时对象；共享 StringBuilder 时必须成对撤销。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q022_traverse_generateParenthesis.java