import java.util.*;

public class Solution {
    private List<String> result = new ArrayList<>();
    
    public List<String> generateParenthesis(int n) {
        backtrack(n, 0, 0, new StringBuilder());
        return result;
    }
    
    private void backtrack(int n, int left, int right, StringBuilder sb) {
        // 终止条件：左右括号各用了 n 个
        if (left == n && right == n) {
            result.add(sb.toString());
            return;
        }
        
        // 选择1：放左括号（还有左括号可用）
        if (left < n) {
            sb.append('(');
            backtrack(n, left + 1, right, sb);
            sb.deleteCharAt(sb.length() - 1); // 回溯
        }
        
        // 选择2：放右括号（右括号数 < 左括号数，有未配对的左括号）
        if (right < left) {
            sb.append(')');
            backtrack(n, left, right + 1, sb);
            sb.deleteCharAt(sb.length() - 1); // 回溯
        }
    }
}

隐式剪枝分析

这道题没有"尝试了一个非法选择然后回溯"的过程。约束条件 left < n 和 right < left 保证了每次放的字符都是合法的，搜索树的每条路径都对应一个（部分）有效括号串。

朴素暴力是：枚举所有 2n 位的二进制串（( 或 )），生成 2^(2n) 个串，然后过滤出有效的。这里的"隐式剪枝"是：通过约束条件，在生成过程中就只产生有效串，直接把搜索空间从 2^(2n) 降到 C(n)（第 n 个卡特兰数）。

复杂度分析

时间复杂度： O(C(n) × n) = O(4^n / sqrt(n))，C(n) 个结果，每个长度 2n，生成时间 O(n)。
空间复杂度： O(n)，递归栈深度为 2n，StringBuilder 长度 O(n)。

三、解法二：迭代 BFS（层次扩展）

思路

将 n 对括号的问题分解：从 1 对括号开始，每次用已有的合法括号组合构建更长的组合。

对于 n 对括号的合法组合，可以从 k 对（k < n）的合法组合递推。具体：枚举第一个 () 包含的左括号数 k，将 n 对组合分解为：( + k 对括号的合法组合 + ) + (n-1-k) 对括号的合法组合。

代码（记忆化递归）

import java.util.*;

public class Solution_Memo {
    private Map<Integer, List<String>> memo = new HashMap<>();
    
    public List<String> generateParenthesis(int n) {
        return generate(n);
    }
    
    private List<String> generate(int n) {
        if (n == 0) return Collections.singletonList("");
        if (memo.containsKey(n)) return memo.get(n);
        
        List<String> result = new ArrayList<>();
        // 分解：左括号内包含 k 对，左括号外（右侧）包含 n-1-k 对
        for (int k = 0; k < n; k++) {
            for (String inner : generate(k)) {
                for (String outer : generate(n - 1 - k)) {
                    result.add("(" + inner + ")" + outer);
                }
            }
        }
        
        memo.put(n, result);
        return result;
    }
}

分解公式： 任何合法括号串都可以表示为 (A)B 的形式，其中 A 是 k 对括号的合法组合，B 是 n-1-k 对括号的合法组合，k 从 0 到 n-1。这正是卡特兰数的递推公式：C(n) = sum(C(k) × C(n-1-k), k=0..n-1)。

Mermaid 图：分解过程

复杂度分析

时间复杂度： O(C(n) × n)（忽略字符串拼接），与回溯相同。但由于每个子问题只计算一次（记忆化），实际重复计算大幅减少。
空间复杂度： O(C(n) × n)，存储所有子问题的结果。

四、解法三：动态规划（字符统计）

代码（DP 构建）

import java.util.*;

public class Solution_DP {
    public List<String> generateParenthesis(int n) {
        List<List<String>> dp = new ArrayList<>();
        dp.add(Collections.singletonList("")); // dp[0] = [""]
        
        for (int i = 1; i <= n; i++) {
            List<String> cur = new ArrayList<>();
            for (int k = 0; k < i; k++) {
                for (String inner : dp.get(k)) {
                    for (String outer : dp.get(i - 1 - k)) {
                        cur.add("(" + inner + ")" + outer);
                    }
                }
            }
            dp.add(cur);
        }
        
        return dp.get(n);
    }
}

这与记忆化递归等价，只是改用了迭代的方式构建 dp 表。

复杂度分析

与记忆化递归相同：O(C(n) × n) 时间，O(C(n) × n) 空间。

五、举一反三

卡特兰数应用场景

问题	卡特兰数含义
n 对括号的合法组合数	C(n)
n+1 个叶子的二叉树形状数	C(n)
凸 n+2 边形三角剖分数	C(n)
n×n 方格不越过对角线的路径数	C(n)
n 个元素的出栈顺序数	C(n)

括号类相关题目

LeetCode 20 有效括号：判断给定括号串是否有效，用栈O(n)。
LeetCode 32 最长有效括号：找最长有效括号子串，DP或栈，O(n)。
LeetCode 301 删除无效括号：删除最少字符使括号有效，BFS+剪枝。

六、踩坑实录

坑一：StringBuilder 的回溯必须用 deleteCharAt

// 正确：精确删除最后一个字符
sb.deleteCharAt(sb.length() - 1);

// 错误：不能用 String 直接操作（String 不可变，没法高效"删除"）
String s = s.substring(0, s.length() - 1); // 每次 O(n)，且逻辑错误（s是参数）

用 StringBuilder 是因为它可以 O(1) 追加字符和删除末尾字符，比用 String + 参数传递更高效。

坑二：right < left 的条件判断

右括号的约束是"当前右括号数严格小于左括号数"，不是"right <= left"。等号时说明所有左括号都已配对，不能再放右括号（否则会多出右括号）。

坑三：终止条件是 leftn && rightn，不是 length==2n

虽然两者等价（满足约束时 leftn && rightn 必然有 length2n），但用 left==n && right==n 更语义明确，也更安全（如果约束条件有 bug，length2n 可能记录无效结果）。

坑四：递推公式中 k 的范围

在分解法中，k 从 0 到 n-1（不包含 n），因为"左括号内"和"左括号外"一共 n-1 对（整体第一个 () 算1对）。如果 k 从 0 到 n，会包含 k=n 的情况（左括号外为 -1 对），逻辑错误。

七、总结

括号生成展示了回溯的一种特殊形式——"只生成合法状态"的 DFS。与其说这是"回溯"，不如说是"约束引导的深度优先搜索"。

三种解法的本质关系：

回溯：从左到右逐字符，约束保证每步合法，终止时记录。
分解递推：将 n 对分解为两个子问题，基于卡特兰递推公式。
DP：迭代版的分解递推，避免递归栈。

三者时间复杂度相同（都是 O(C(n) × n)），但空间使用不同。面试中首选回溯，代码最简洁直观。

解法	时间复杂度	空间复杂度	推荐
回溯	O(4^n/√n)	O(n)	强烈推荐
记忆化递归	O(4^n/√n)	O(4^n×n/√n)	了解
动态规划	O(4^n/√n)	O(4^n×n/√n)	了解

补充深入讲解：括号生成与卡特兰数的深层联系

卡特兰数的完整推导

N 对括号的合法序列数等于第 N 个卡特兰数 C(N) = C(2N,N)/(N+1)。这个公式来自一个优美的计数论证。

考虑所有长度为 2N 的由 N 个左括号和 N 个右括号组成的序列（总共 C(2N,N) 个），其中有一部分是合法的括号序列（任何前缀中左括号数不少于右括号数），另一些是不合法的。

通过"反射论证"（Reflection Argument）可以证明：不合法的序列总数恰好等于长度为 2N、由 N-1 个左括号和 N+1 个右括号组成的序列总数，即 C(2N, N-1)。

合法序列数 = 总序列数 - 不合法序列数 = C(2N,N) - C(2N,N-1) = C(2N,N)/(N+1) = C(N)。

反射论证的核心思想：对于任意一个不合法的括号序列（存在某个前缀中右括号多于左括号），找到第一个"右多一"的位置，从该位置之后的序列做"交换"（把左括号变右括号、右括号变左括号），得到一个 N-1 左、N+1 右的序列。这个对应关系是双射（一一对应），所以两个集合大小相等。

为什么回溯是括号生成的最优方法

括号生成（输出所有合法序列）的时间复杂度下界是 O(C(N) × N)，因为有 C(N) 个结果，每个结果长度 2N。任何算法都不可能比这快。

回溯方法恰好达到这个下界：只有合法的选择才会继续递归（左括号未用完时可以加左括号，右括号个数小于左括号时可以加右括号），没有任何无效的分支被探索。这是因为括号生成的约束非常简单（只看左括号和右括号的数量关系），剪枝极为彻底，没有任何浪费。

动态规划也可以生成所有括号序列，但通常需要额外的空间存储中间状态，而回溯只需 O(N) 的递归栈，更省空间。

括号序列的等价结构

合法括号序列与其他很多组合结构等价，都被卡特兰数计数：

满二叉树的形态：N+1 个叶子的满二叉树（每个内节点恰好有两个子节点）共有 C(N) 种不同的形态。括号序列 ( ) 对应一次"左分叉"，这种对应关系是双射。

出栈序列：N 个不同元素按 1,2,...,N 的顺序入栈，合法的出栈序列（不需要全部出栈，但满足栈的先进后出约束）共有 C(N) 种。

非交叉分割：将正多边形的 N+2 条边通过 N-1 条不相交的对角线分割成三角形，共有 C(N) 种方法。

这些等价结构说明卡特兰数是一个深刻的数学对象，连接着组合数学的多个领域。在面试中，如果能说出"括号序列数是第 N 个卡特兰数"并简单解释，会给面试官留下深刻印象。

括号匹配在工程中的应用

括号匹配是编译器和解析器的核心功能。在词法分析阶段，编译器需要检查括号（以及大括号、方括号）的合法性；在语法分析阶段，括号的嵌套结构对应了抽象语法树（AST）的层级关系。

LeetCode 22 的回溯框架，在工程上对应了"生成所有合法的嵌套结构"的需求。例如：

代码自动补全：在用户输入 ( 后，自动补全建议的可能括号结构。
测试用例生成：生成所有 N 层嵌套函数调用的合法形式，用于测试解析器的边界情况。
正则表达式构建：生成所有 N 个捕获组的合法正则表达式模板。

从这个角度看，括号生成不只是抽象的算法题，而是编译技术和程序分析领域的基础工具。

括号生成的变形：不同类型的括号

LeetCode 22 只有一种括号（圆括号）。如果有三种括号（圆括号、方括号、大括号），每种各 N 对，要求所有括号都正确匹配，方案数和生成算法会如何变化？

方案数不再是卡特兰数，而是更复杂的计数结果。生成算法需要在回溯时维护每种括号的开括号栈，确保关闭括号时只关闭正确类型的最近未关闭开括号。这是 LeetCode 22 的进阶变形，在面试中偶尔出现。

括号生成的隐式剪枝与显式剪枝的对比

括号生成（LeetCode 22）的回溯只有两种选择：加左括号或加右括号。回溯的剪枝也只有两种：当左括号数已达 n 时不能再加左括号（left == n），当右括号数已达 left 时（即右括号数等于已用左括号数，再加右括号会导致不匹配）不能再加右括号。

这两个条件非常简单，但它们恰好是括号序列合法性的充要条件：

任何时刻，已用左括号数不超过 n（左括号不超限）。
任何时刻，已用右括号数不超过已用左括号数（括号不提前关闭）。
最终，已用左括号数等于已用右括号数等于 n（完整的 n 对括号）。

满足这三个条件的字符串恰好就是合法的括号序列，不多不少。因此括号生成的回溯没有任何"无效分支"——每条探索路径要么已经是合法序列的前缀，要么因为违反约束而被立即剪枝，没有任何"走错路再回头"的情况。这使得括号生成的回溯是几乎理想的剪枝回溯，时间复杂度等于输出大小 O(C(N) × N)，达到理论最优。

括号生成的记忆化优化与动态规划

括号生成也可以用动态规划实现，虽然不如回溯直观。定义 dp[n] 为所有 n 对括号的合法序列集合，递推关系是：dp[n] = { "(" + dp[i] + ")" + dp[n-i-1] | i=0,1,...,n-1 }。

含义：第一个左括号和它匹配的右括号之间有 dp[i] 中的某个序列（i 对括号），这对括号之后跟着 dp[n-i-1] 中的某个序列（n-i-1 对括号）。将 i 从 0 到 n-1 枚举，合并所有可能的序列，就得到 dp[n]。

这个 DP 递推直接对应了括号序列的递归结构（找到第一个左括号匹配的右括号，将序列分为内部和后续两部分），与卡特兰数的递推关系完全对应。在面试中能说出这个 DP 推导，会展示对括号结构深层理解。

括号生成的代码简洁性

括号生成（LeetCode 22）的回溯代码是回溯类题目中最简洁的之一：约束只有两个（左括号不超 n，右括号不超已用左括号数），候选只有两个（加左括号或加右括号），终止条件只有一个（总长度达到 2n）。代码不超过15行，却能生成所有合法括号序列。

这种简洁性来自于问题本身的约束形式非常简单（只依赖于左右括号的数量，不依赖于序列的具体内容）。与之对比，全排列的约束依赖于"哪些元素已被使用"（需要 visited 数组），数独的约束依赖于"棋盘的整体状态"（需要约束矩阵）。

在回溯类题目中，约束越简单，代码越短，运行越快，正确性越容易验证。括号生成的简洁性使它成为面试中的高频题——代码量少，但考查了回溯的核心概念（做选择、剪枝、撤销），性价比极高。

卡特兰数的记忆技巧

卡特兰数 C(N) 的三个等价公式：C(N) = C(2N,N)/(N+1)；C(N) = C(2N,N) - C(2N,N-1)；C(0)=1，C(N) = sum(C(i)×C(N-1-i))，i=0到N-1。

最容易记忆的是第三个递推公式：括号序列 "(X)Y" 中，X 是 i 对括号的合法序列，Y 是 N-1-i 对括号的合法序列，i 从 0 到 N-1 枚举。这个公式同时是动态规划解法的基础和卡特兰数的定义递推，理解了它就同时记住了公式和算法。