括号生成如何用回溯法求解？（LeetCode 22）

简化版

给 n 对括号，生成所有合法的括号组合。用回溯逐个添加字符，把「合法性」直接做成剪枝：左括号数量没到 n 就能加 (；右括号数量小于已用左括号数才能加 )（保证任何前缀里 ) 都不多于 (）。长度到 2n 就收集一个解。这样生成的全是合法括号串，不用先全排再筛。解的个数是卡特兰数。

详细版

List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    backtrack(new StringBuilder(), 0, 0, n, res);
    return res;
}
// open：已用左括号数；close：已用右括号数
void backtrack(StringBuilder sb, int open, int close, int n, List<String> res) {
    if (sb.length() == 2 * n) {                // 用满 n 对
        res.add(sb.toString());
        return;
    }
    if (open < n) {                            // 还能加左括号
        sb.append('(');
        backtrack(sb, open + 1, close, n, res);
        sb.deleteCharAt(sb.length() - 1);      // 撤销
    }
    if (close < open) {                        // 右括号不能超过左括号
        sb.append(')');
        backtrack(sb, open, close + 1, n, res);
        sb.deleteCharAt(sb.length() - 1);      // 撤销
    }
}

两条剪枝规则保证只生成合法串：open < n 才加 (；close < open 才加 )。
结束条件：长度到 2n（此时必然 open==close==n）。
用 StringBuilder 做「追加 / 删末尾」实现选择与撤销。
解的数量 = 第 n 个卡特兰数 Cₙ = C(2n, n) / (n+1)。

完整版教学

一、问题与暴力思路

括号生成：n=3 的所有合法组合是 ["((()))","(()())","(())()","()(())","()()()"]，共 5 个。

暴力思路：2n 个位置每个填 ( 或 )，共 2^(2n) 种，再逐一判断是否合法。这能做但浪费——绝大多数组合不合法。更好的办法是在生成过程中就只走合法的路，用剪枝把非法分支从决策树上直接砍掉。

二、剪枝生成：把合法性约束嵌进递归

「合法括号串」的充要条件是：任意前缀中，右括号数量都不超过左括号数量；且最终左右各 n 个。 我们把这两条直接变成「什么时候允许加左括号 / 加右括号」的判断，嵌进递归里。这样每一步做的选择都保证当前前缀合法，走到 2n 长度时自然是一个完整的合法串。

维护两个计数：open（已经用的左括号数）、close（已用右括号数）。

三、两条剪枝规则：open < n 与 close < open

加左括号的条件：open < n。 左括号总共只有 n 个，用满了就不能再加。
加右括号的条件：close < open。 右括号只能去「闭合」一个已经存在的、还没配对的左括号。只要已用的右括号数 close 还小于左括号数 open，就有未闭合的左括号可配，能加 )；一旦 close == open，再加 ) 就会出现「右比左多」的非法前缀，禁止。

这两条规则合起来，保证任何时刻前缀都合法，且最终 open 和 close 都恰好到 n。

易错点：右括号的条件是 close < open（和左括号数比），不是 close < n。用 close < n 会放出像 ())( 这样的非法串。

四、代码与回溯（用 StringBuilder 撤销）

用 StringBuilder 承载路径：加字符用 append，撤销用 deleteCharAt(length-1)，和 path.add / removeLast 一个道理，成对出现。

因为每一步最多两个分支（加左、加右），且都带合法性判断，决策树上的每条路径都直达一个合法解，没有无效叶子，效率很高。结束条件只需判长度到 2n——此时 open 必等于 close 必等于 n，无需额外校验。

五、解的数量：卡特兰数

n 对括号的合法组合数正好是第 n 个卡特兰数：

Cₙ = C(2n, n) / (n + 1)

例如 C₃ = C(6,3)/4 = 20/4 = 5，和上面枚举的 5 个吻合。卡特兰数还出现在「n 个节点的不同二叉搜索树数量」「合法出栈序列数」「凸多边形三角剖分数」等一大类问题里——它们都能对应到「括号匹配 / 不越界的路径」结构，是组合数学里的高频常客。

六、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：任意前缀都满足 0≤close≤open≤n；只有 open=close=n 时才形成完整合法串。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：n=3 只有 5 个叶子，对应卡特兰数 C3=5，而非暴力 2^6=64 个串全部检查。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

七、复杂度、剪枝代价与实现边界

关键实现边界是：StringBuilder 撤销要按加入前长度恢复；n=0 通常返回一个空串；结果数量是 Catalan 数。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

八、常见误区与追问

误区：左右括号各不超过 n 就足够。 还必须保证任何前缀右括号数不超过左括号。
误区：生成完 2n 位再检查更简单且同样快。 会遍历大量必然非法前缀。
误区：复杂度可写 O(2^n)。 解数是 Catalan Cn，复制每个长度 2n，常写 O(n·Cn)。
追问：close<open 为什么安全？ 确保每个前缀都能被解释为尚未闭合完的合法括号序列。
追问：能先放右括号吗？ 空前缀不满足 close<open，因此不允许。
追问：怎样避免字符串频繁创建？ 使用可变缓冲区并在回溯时恢复长度。

九、加强记忆

括号生成回溯：维护 open（左括号数）、close（右括号数），两条剪枝——open < n 才加 (、close < open 才加 )（右括号绝不多于左括号，注意是比 open 不是比 n），长度到 2n 收集。合法性嵌进递归、边生成边剪枝，不必先全排再筛。解的个数是卡特兰数 C(2n,n)/(n+1)，它和不同 BST 数、合法出栈序列数同源。

简化版

详细版