平衡括号算法

Question

我一直在研究回溯/DFS算法并遇到了平衡括号问题。

此代码片段根据参数

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

。

---

我错过了什么？

Answer 1

 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 fourthd level: only the last branch is allowed, so `(())` 

      The second level again: last branch is allowed too, so `()` is created
           The third level: middle branch is allowed, so `()(` 
                The fourthd level: only the last branch is allowed, so `()()`