javascript 平衡Parantheses算法

zz2j4svz 于 11个月前发布在 Java

关注(0)|答案(4)|浏览(79)

我一直在研究回溯/ 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。
我错过了什么？

JavaScript

来源：https://stackoverflow.com/questions/77177822/balanced-parantheses-algorithm

4条答案

按热度按时间

nhaq1z211#

The first level of recursion: the only allowed branch is `if (usedOpen < n) `, so '(' is created
      The second level: `if (usedOpen < n)` is allowed, so `((` is created
           The third level: only the last branch is allowed, so `(()` 
                The fourth level: only the last branch is allowed, so `(())` 
                   Now the fifth level,  res.push(cur) is executed,
                program returns to the fourth level (nothing to do)
            third (nothing to do)

      And second level again: last branch is allowed too, so `()` is created
           The third level: middle branch is allowed, so `()(` 
                The fourth level: only the last branch is allowed, so `()()` 
                    the fifth level,  res.push(cur) is executed
                program returns to upper levels

赞(0）回复(0）举报 12个月前

kuuvgm7e2#

实际上之后就不会复发了。下面是递归调用树：

findCombo（2，“"，0，0）
findCombo（2，“（“，1，0）
findCombo（2，“（（“，2，0）
findCombo（2，“（（）"，2，1）
findCombo（2，“（（））"，2，2）
=> push_back（“（（））”）//没有递归后
findCombo（2，“（）"，1，1）
findCombo（2，“（“，2，1）
findCombo（2，“（）（）"，2，2）
=> push_back（“（）（）”）//没有递归后

赞(0）回复(0）举报 12个月前

zlhcx6iw3#

将对findCombo的每个调用都看作具有不同的名称可能会有所帮助;例如findCombo_0_0、findCombo_1_1等;因为每次调用它，它都会在计算系统中获得一个新的堆栈帧。并不是同一个findCombo调用在执行所有操作，它有很多;它们都有相同的执行方法，存储在名称findCombo下。
findCombo参数值根本不会减少或更改。名为findCombo的执行方法会产生对同一例程的各种调用，因此我们将其描述为递归。
在这种特殊情况下，例程不提供或使用此类调用的返回值，而是（在基本情况下）将字符串值推送到在所有这些调用之外定义的数组。

赞(0）回复(0）举报 12个月前

svujldwt4#

下面是递归调用的完整扩展，其中评估了三个条件（表示为A，B，C）。

Find(2, '', 0, 0)
. A false
. B true
. . Find(2, '(', 1, 0)
. . . A false
. . . B true
. . . . Find(2, '((', 2, 0)
. . . . . A false
. . . . . B false
. . . . . C true
. . . . . . Find(2, '(()', 2, 1)
. . . . . . . A false
. . . . . . . B false
. . . . . . . C true
. . . . . . . . Find(2, '(())', 2, 2)
. . . . . . . . . A done
. . . C true
. . . . Find(2, '()', 1, 1)
. . . . . A false
. . . . . B true
. . . . . . Find(2, '()(', 2, 1)
. . . . . . . A false
. . . . . . . B false
. . . . . . . C true
. . . . . . . . Find(2, '()()', 2, 2)
. . . . . . . . . A done
. . . . . C false
. C false

赞(0）回复(0）举报 12个月前

我来回答

javascript 平衡Parantheses算法

4条答案

相关问题

热门标签

最新问答