javascriptalgorithmrecursiondepth-first-searchbacktracking

Balanced Parantheses Algorithm

I've been studying backtracking / DFS algorithms and came across the balanced parentheses problem.

This snippet populates an array with all valid parentheses combos based on the value of argument 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 );
    }
}

So calling the above with n = 2:

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

correctly prints: [ '(())', '()()' ]

And calling it with n = 3:

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

correctly prints: [ '((()))', '(()())', '(())()', '()(())', '()()()' ]

My question is; how does findCombo() continue to iterate after the 1st push to the res array? I've traced execution by hand and recursion should stop iterating once res.push is executed since at that point usedOpen = n and usedClose = n.

In other words, I can't see how any subsequent array element gets created, e.g. '()()' for n = 2.

What am I missing?

Solution

  • Actually it doesn't recur after. Here is the recursive calls tree: