我一直在研究回溯/ DFS算法,偶然发现了balanced parentheses problem。
此代码段根据参数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);
正确打印:[ '((()))', '(()())', '(())()', '()(())', '()()()' ]
我的问题是; findCombo()
如何在第一次推送到res
数组后继续迭代?我已经手动跟踪了执行过程,一旦res.push
被执行,递归就应该停止迭代,因为在那个时候usedOpen = n
和usedClose = n
。
换句话说,我看不到任何后续的数组元素是如何创建的,例如。'()()'
为n = 2
。
我错过了什么?
4条答案
按热度按时间nhaq1z211#
kuuvgm7e2#
实际上之后就不会复发了。下面是递归调用树:
zlhcx6iw3#
将对
findCombo
的每个调用都看作具有不同的名称可能会有所帮助;例如findCombo_0_0
、findCombo_1_1
等;因为每次调用它,它都会在计算系统中获得一个新的堆栈帧。并不是同一个findCombo
调用在执行所有操作,它有很多;它们都有相同的执行方法,存储在名称findCombo
下。findCombo
参数值根本不会减少或更改。名为findCombo
的执行方法会产生对同一例程的各种调用,因此我们将其描述为递归。在这种特殊情况下,例程不提供或使用此类调用的返回值,而是(在基本情况下)将字符串值推送到在所有这些调用之外定义的数组。
svujldwt4#
下面是递归调用的完整扩展,其中评估了三个条件(表示为
A
,B
,C
)。