本文深入剖析生成n对合法括号的所有组合的递归回溯算法，重点解释为何在首次将结果推入数组后递归仍能继续执行并生成其余有效组合。
本文深入剖析生成n对合法括号的所有组合的递归回溯算法，重点解释为何在首次将结果推入数组后递归仍能继续执行并生成其余有效组合。
生成合法括号组合是回溯（Backtracking）与深度优先搜索（DFS）的经典入门问题。其核心在于：每一步只做合法选择，并在到达边界时保存解，随后自动回退尝试其他路径。关键误区在于认为 res.push(cur) 执行后整个递归就“终止”了——实际上，它只是当前递归分支的成功出口，而函数调用栈会自然向上回退（return），回到上一层未执行完的分支中，继续探索其他可能性。
以下是对 findCombo(n, cur, usedOpen, usedClose) 的完整逻辑解析（以 n = 2 为例）：
✅ 合法性约束决定分支走向
算法依赖两个关键剪枝条件：
- usedOpen < n → 可添加 '('（只要左括号未用完）；
- usedOpen > usedClose && usedClose < n → 可添加 ')'（右括号数必须严格小于左括号数，且未达上限）。
这两个条件共同保证了任意前缀中 '(' 数量 ≥ ')' 数量，且最终二者均为 n —— 这正是「平衡」的数学定义。
? 回溯过程可视化（n = 2）
调用 findCombo(2, "", 0, 0) 启动：
第1层：cur="", usedOpen=0, usedClose=0
→ 满足 usedOpen < 2 → 进入 findCombo(2, "(", 1, 0)-
第2层：cur="(", usedOpen=1, usedClose=0
→ 可选 '('（→ "(( "）或 ')'（→ "()"）
⚠️ 注意：这是分叉点！算法不会只走一条路。左支（"(( "）：
→ 第3层："((" → 只能加 ')'（因 usedOpen=2, usedClose=0, 2>0）→ "(())"
→ 第4层："(())" → usedOpen===usedClose===2 → res.push("(())")，返回
→ 此支结束。右支（"()"）（回到第2层，执行第二个 if 分支）：
→ 第3层：cur="()", usedOpen=1, usedClose=1
→ 此时 usedOpen < 2 → 可加 '(' → "()("
→ 第4层："()(" → usedOpen=2, usedClose=1, 2>1 → 可加 ')' → "()()"
→ 第5层："()()" → 达终态 → res.push("()()")
可见，res.push() 并非全局终止，而是当前路径的终点；函数通过隐式 return 回到上层调用点，继续执行该层剩余的 if 判断（如第2层在完成 "(( " 后，仍会执行 if (usedOpen > usedClose...) 尝试 "()"）。
? 关键理解：递归 ≠ 单线程直行
- 每次函数调用都拥有独立的参数副本（cur, usedOpen, usedClose）；
- res.push() 不影响调用栈结构，仅修改共享数组；
- 所有未完成的 if 分支在对应层级依然有效，等待被依次评估。
✅ 完整可运行示例（含初始化封装）
function generateParentheses(n) {
const res = [];
function findCombo(cur, usedOpen, usedClose) {
// 终止条件：已生成 n 对括号
if (usedOpen === n && usedClose === n) {
res.push(cur);
return; // 显式 return 更清晰（虽非必需）
}
// 选择1：添加左括号
if (usedOpen < n) {
findCombo(cur + '(', usedOpen + 1, usedClose);
}
// 选择2：添加右括号（需保证不破坏平衡）
if (usedOpen > usedClose && usedClose < n) {
findCombo(cur + ')', usedOpen, usedClose + 1);
}
}
findCombo("", 0, 0);
return res;
}
console.log(generateParentheses(2)); // ['(())', '()()']
console.log(generateParentheses(3)); // 5 个组合⚠️ 注意事项
- res 必须在递归函数外部声明（或作为闭包变量），否则每次递归都会新建空数组；
- 参数 cur 使用字符串拼接（不可变），天然实现“路径快照”，无需手动回溯撤销（如 cur.pop()）；
- 时间复杂度为卡特兰数 $ C_n = \frac{1}{n+1}\binom{2n}{n} $，空间复杂度为 $ O(n) $（递归栈深度）。
掌握这一回溯模型，不仅能解决括号问题，更为理解 N 皇后、数独、子集生成等经典 DFS 问题奠定坚实基础。
