Question 252798 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – 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?

Tags:

3

Answers


  1. 0 
     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
    Login or Signup to reply.
  2. 0

    Actually it doesn’t recurse after.
    Here is the recursive calls tree:

    • findCombo(2, “”, 0, 0)
    • findCombo(2, “(“, 1, 0)
    • findCombo(2, “((“, 2, 0)
    • findCombo(2, “(()”, 2, 1)
    • findCombo(2, “(())”, 2, 2)
    • => push_back(“(())”) //no recursion after
    • findCombo(2, “()”, 1, 1)
    • findCombo(2, “()(“, 2, 1)
    • findCombo(2, “()()”, 2, 2)
    • => push_back(“()()”) //no recursion after
    Login or Signup to reply.
  3. 0

    Here is the complete expansion of the recursive calls, with the three conditions evaluated.

    Find(2, '', 0, 0)
. false
. true
. . Find(2, '(', 1, 0)
. . . false
. . . true
. . . . Find(2, '((', 2, 0)
. . . . . false
. . . . . false
. . . . . true
. . . . . . Find(2, '(()', 2, 1)
. . . . . . . false
. . . . . . . false
. . . . . . . true
. . . . . . . . Find(2, '(())', 2, 2)
. . . . . . . . . done
. . . true
. . . . Find(2, '()', 1, 1)
. . . . . false
. . . . . true
. . . . . . Find(2, '()(', 2, 1)
. . . . . . . false
. . . . . . . false
. . . . . . . true
. . . . . . . . Find(2, '()()', 2, 2)
. . . . . . . . . done
. . . . . false
. false
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search