回溯/DFS生成合法括号算法：递归后续执行逻辑疑问

数据老陈

2026-7-9

关于回溯/DFS生成合法括号组合的递归疑问

我正在学习回溯/DFS算法，遇到了LeetCode上的生成括号问题。

以下代码片段可根据参数n的值，将所有合法括号组合存入数组：

function findCombo(n, cur, usedOpen, usedClose) {
    if (usedOpen === n && usedClose === n) {
        res.push(cur);
    } 
    if (usedOpen < n) {
        findCombo(n, cur + '(', usedOpen + 1, usedClose );
    }
    if (usedOpen > usedClose && usedClose < n) {
        findCombo(n, cur + ')', usedOpen, usedClose + 1 );
    }
}

当调用n = 2时：

let res = [];
findCombo(2, "", 0, 0);
console.log(res);

正确输出：[ '(())', '()()' ]

调用n = 3时：

let res = [];
findCombo(3, "", 0, 0);
console.log(res);

正确输出：[ '((()))', '(()())', '(())()', '()(())', '()()()' ]

我的问题是：首次向res数组推入元素后，findCombo()为何还能继续执行生成后续组合？我手动追踪执行流程后认为，当执行res.push时，usedOpen = n且usedClose = n，递归应该停止。比如我无法理解n=2时'()()'这类后续数组元素是如何生成的。

我忽略了什么？

你忽略了递归函数的调用栈特性——当一个递归分支执行完毕（比如第一次推入'(())'的分支），程序会回到这个分支的上一层函数调用，继续执行后续未完成的代码逻辑，也就是其他递归分支。

拿n=2的情况一步步拆解：

初始调用findCombo(2, "", 0, 0)，进入函数后，不满足终止条件，执行第一个if：调用findCombo(2, "(", 1, 0)。
进入新调用，仍不满足终止条件，执行第一个if：调用findCombo(2, "((" ,2, 0)。
进入这个调用，usedOpen=2但usedClose=0，不满足终止条件；第一个if因usedOpen不小于n跳过，执行第二个if：调用findCombo(2, "(()",2,1)。
进入这个调用，还是不满足终止条件，第一个if跳过，执行第二个if：调用findCombo(2, "(())",2,2)。
现在满足终止条件，把"(())"推入res，这个函数执行完毕，回到上一层调用（步骤3的函数）。
步骤3的函数执行完毕，回到步骤2的函数。
步骤2的函数在调用完findCombo(2, "((" ,2,0)后，继续执行第二个if：usedOpen(1) > usedClose(0)且usedClose<2，调用findCombo(2, "()",1,1)。
进入这个调用，不满足终止条件，执行第一个if：调用findCombo(2, "()(",2,1)。
进入这个调用，usedOpen=2，usedClose=1，第一个if跳过，执行第二个if：调用findCombo(2, "()()",2,2)，满足终止条件，把"()()"推入res。
后续逐层返回，所有分支执行完毕，最终res就是['(())','()()']。

核心是：每个递归调用完成后，程序会回到父调用，继续执行父调用中未完成的代码（后续的if分支），而不是整个递归直接停止。你手动追踪时可能只跟进了第一个成功分支，没考虑到分支执行完后回到上层尝试其他路径的过程——这正是回溯算法的核心：尝试一条路走到头，再退回来走另一条路。

内容的提问来源于stack exchange，提问作者n00b