)
本题采用深度优先搜索DFS回溯剪枝算法又称“左右括号计数配对法”或“严格平衡状态决策树法”解决合法括号组合的生成问题。其核心本质是在回溯搜索空间中利用“右括号数量在任意前缀中不得超过左括号数量”和“左右括号总上限为 n”的双重单调性约束通过原地字符数组实现无回溯擦除开销的剪枝探索。当前提供的源码实现了在时间复杂度 O(4^n / (n * 根号 n)) 和额外空间复杂度 O(n) 条件下的全局状态树搜索最终走向是精准输出所有合法的括号组合。一、 问题本质与数据模型对于给定对数 n 的括号生成问题其组合空间可被抽象为一个深度为 2n 的二叉决策树。在树的每一层只有两种物理选择放置左括号 ( 或放置右括号 )。如果采用无差别的全排列暴力搜索将生成 2^(2n) 种可能的字符序列然后必须对每个序列执行 O(n) 的合法性校验如使用栈这会导致极高的时间开销与算力浪费。为了破除这种盲目搜索带来的指数级状态冗余算法引入了基于计数状态的“剪枝模型”。通过维护已放置的左括号数 left 和右括号数 right定义以下两条物理安全边界上限约束左括号数量 left 绝不能超过物理上限 n即在 left n 时才能放置左括号。合法配对约束右括号数量 right 在任何瞬时时刻都必须严格小于当前已放置的左括号数量 left即在 right left 时才能放置右括号。这两条边界充当了物理决策树的守卫盾牌直接将所有不合法的“幽灵分支”剪除在萌芽状态确保搜索树在到达叶子节点时产生的序列必然是天然合法的。二、 算法演进对比在解决括号生成问题的场景中剪枝回溯法在时空资源的利用率上达到了平衡极限解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷暴力回溯 合法性校验O(2^(2n) * n)O(n)递归生成所有可能序列触底后利用栈或计数器进行合法性检查生成了大量完全不合法的垃圾分支算力极度浪费剪枝回溯当前解法O(4^n / (n * 根号 n))O(n)利用左右括号计数实时剪枝确保探索的分支均是合法括号序列的前缀属于括号回溯算法的理论极限在极大规模输入下受限于卡特兰数级结果量动态规划 (DP)O(4^n / (n * 根号 n))O(4^n / (n * 根号 n))利用 dp[i] ( dp[p] ) dp[q]其中 p q i - 1拼接历史子状态结果空间开销极大因需要显式存储所有历史组合列表进行高频物理拼接三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于 dfs 方法内的计数边界和字符定位其内部决策分支证明如下1. 命中收集分支if (right n)执行ans.add(new String(path)); return;物理意义当右括号放置数量达到上限 n 时由于合法配对约束的物理存在此时左括号数量 left 必然也达到了 n。这说明整条路径已完整闭合且安全触底将原地字符数组 path 转换为字符串并装入结果集。2. 左侧深探分支if (left n)执行path[left right] (; dfs(ans, path, left 1, right, n);数学证明只要当前的左括号配额还未用完left n在决策树的当前深度 left right 处放置左括号 ( 永远是物理安全的。它不会破坏后续括号配对的正确性所以执行状态转移左括号计数加 1。3. 右侧收敛分支if (right left)执行path[left right] ); dfs(ans, path, left, right 1, n);数学证明要使得括号闭合右括号在任意前缀中必须能够找到与其配对的未闭合左括号。只有在已放置右括号数量严格小于已放置左括号数量right left时放置右括号 ) 才不会导致括号乱序越界。此判断将“未配对即闭合”的违规分支直接抹杀。4. 无需显式回溯擦除证明仔细观察源码可以发现这里没有出现常规回溯算法中的“物理状态清理”如在 DFS 退出后将 path 元素置空。数学证明这是因为我们在递归时下一个状态写入的下标为 left right。由于单向深度步进新一轮写入的字符在物理上会直接覆盖旧分支遗留下的历史字符相当于实现了隐式的原地状态更新免去了擦除带来的冗余赋值开销。四、 算法执行状态机步进示例以 n 2 为例预期生成 [ ()(), (()) ] 组合回溯调用栈及状态演变过程如下表所示步骤当前坐标 (left right)状态计数 (left, right)当前写入字符分支校验判定条件调用栈及 path 物理存储状态初始0(0, 0)-满足 left 2栈深: [ (0,0) ], path: [ , , , ]10(0, 0)(写入进入下一层栈深: [ (0,0) - (1,0) ], path: [ (, , , ]21(1, 0)(满足 left 2写入栈深: [ (1,0) - (2,0) ], path: [ (, (, , ]32(2, 0))无法写左(2 2)满足 right left写右栈深: [ (2,0) - (2,1) ], path: [ (, (, ), ]43(2, 1))满足 right left写右并触底栈深: [ (2,1) - (2,2) ], path: [ (, (, ), ) ] -收集 (())并回溯51(1, 0))回溯至步骤 1满足 right left写右栈深: [ (1,0) - (1,1) ], path: [ (, ), ), ) ]注后两位为覆盖前的历史字符62(1, 1)(满足 left 2写入覆盖下标 2栈深: [ (1,1) - (2,1) ], path: [ (, ), (, ) ]73(2, 1))满足 right left写入下标 3 并触底栈深: [ (2,1) - (2,2) ], path: [ (, ), (, ) ] -收集 ()()并回溯五、 源码实现import java.util.ArrayList; import java.util.List; class Solution { public ListString generateParenthesis(int n) { ListString ans new ArrayList(); // 物理开辟一个长度为 2n 的字符数组存放当前回溯路径的字符状态 char[] path new char[2 * n]; // 启动深度优先搜索初始化左右括号放置计数均为 0 dfs(ans, path, 0, 0, n); return ans; } private void dfs(ListString ans, char[] path, int left, int right, int n) { // 基准收敛条件当右括号数量达到上限时说明所有括号已配对成功 if (right n) { ans.add(new String(path)); // 原地将字符数组转换为字符串存入结果集 return; } // 剪枝控制 1只要左括号数量未达到最大值 n就可以继续放置左括号 if (left n) { path[left right] (; // 在当前指针位置写入左括号 dfs(ans, path, left 1, right, n); // 递归向下left 计数自增 } // 剪枝控制 2只有当已放置的右括号数小于左括号数时才能放置右括号以保证平衡 if (right left) { path[left right] ); // 在当前指针位置写入右括号 dfs(ans, path, left, right 1, n); // 递归向下right 计数自增 } } }六、 复杂度分析1. 时间复杂度O(4^n / (n * 根号 n))分析在限制性回溯下生成的叶子节点数量等于第 n 个卡特兰数 (Catalan Number)。卡特兰数的通项计算公式为C_n (1 / (n 1)) * (2n 选 n)。利用斯特林公式对组合数进行渐近展开当 n 趋于无穷大时该值渐近于4^n / (n * 根号(pi * n))。在回溯树中除了叶子节点外每个合法叶子节点对应的非叶子节点即其决策树路径上的祖先节点数量与 n 呈线性关系。每一次触底时将字符数组转换为字符串的开销为 O(n)。结论整体时间复杂度被卡特兰数阶严格控制定性为O(4^n / (n * 根号 n))。2. 空间复杂度O(n)分析该解法未使用任何与中间状态成正比的外部独立数据结构而是利用了唯一的char[] path数组原地保存路径字符其物理开销为固定常数阶 O(n)。空间的动态起伏完全取决于隐式的递归调用栈深度。在构建长度为 2n 的括号序列时递归树的最大深度严格限制在2n层。结论最大额外空间复杂度包括系统调用栈与物理路径数组表现为O(n)。
