Interview Questions

Generate all balanced bracket combinations

For this popular algorithm interview question, your goal is to print all possible balanced parenthesis combinations up to N. For example:
## Algorithm

We will implement a recursive function to solve this challenge. The idea is:
## Code

## Running time

The number of sets that can be generated is related to the Catalan numbers. Therefore, an upper bound on the running time of this algorithm is the following formula plus the time needed to append to a string and push to an array.
## Sources

https://www.glassdoor.com/Interview/Write-a-function-Brackets-int-n-that-prints-all-combinations-of-well-formed-brackets...

N = 2
(()), ()()
N = 3
((())), (()()), (())(), ()(()), ()()()

(1) Add a left bracket to a newly created string.
(2) If a left bracket was added, potentially add a new left bracket *and* add a right bracket.
(3) After each of these steps we add the string to an array that stores all bracket combinations.

This recursive solution might be hard to see at first, but using N = 2 as an example, the steps taken are:
N = 2
create (
create ()
N = 1
create ((
create ()(
N = 0
add (())
add ()()
Done when N = 0
var all = []; function parens(left, right, str) { // if no more brackets can be added then add the final balanced string if (left === 0 && right === 0) { all.push(str); } // if we have a left bracket left we add it if (left > 0) { parens(left-1, right+1, str+"("); } // if we have a right bracket left we add it if (right > 0) { parens(left, right-1, str+")"); } } // the parameters parens(x, y, z) specify: // x: left brackets to start adding // y: right brackets we can add only after adding a left bracket // z: the string so far parens(3, 0, ""); all;

arr = [] def parens(left, right, string): # if no more brackets can be added then add the final balanced string if left == 0 and right == 0: arr.append(string) # if we have a left bracket left we add it if left > 0: parens(left-1, right+1, string+"(") # if we have a right bracket left we add it if right > 0: parens(left, right-1, string+")") # the parameters parens(x, y, z) specify: # x: left brackets to start adding # y: right brackets we can add only after adding a left bracket # z: the string so far parens(3, 0, "") print arr

mrdaniel
published this on 2/8/16 **|**

1

Hi ,
I can understand the code flow till the " (()) " output. But How the next one " ()() " is getting printed in javascript ? what happening behind the screen ? Please Explain. To get better understanding like this concepts what i need to learn ? Please share. Thanks in Advance.

Ramaprasath

commented on 07/31/18

0

Ramaprasath after done with the left>0 path its coming back to the right >0 path from where it left its path.for eg in (()) it is coming back to first '(' because it left the code from that point and then it continue from there and add ')' and move to next parens at that place left is 1 so first add '(' and then next parens add ')' and add the string.

pravin10717

commented on 08/20/18

Log in to submit a comment.