Article type: Algorithm

Generate all balanced bracket combinations

mrdaniel published this on 2/8/16
For this popular algorithm interview question, your goal is to print all possible balanced parenthesis combinations up to N. For example:
N = 2 (()), ()() N = 3 ((())), (()()), (())(), ()(()), ()()()

Algorithm

We will implement a recursive function to solve this challenge. The idea is:
(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

Code

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;
Run 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...

Comments (3)

2
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
3
A Python Solution:
combs = []
total = 8

def combinations(left, right, toClose, str=""):
    if toClose < 0 or toClose > total / 2 or left < 0 or right < 0:
        return

    if left + right < 1:
        combs.append(str)
        return

    for s in ['(', ')']:
        str += s
        if s == '(':
            combinations(left - 1, right, toClose + 1, str)
        else:
            combinations(left, right - 1, toClose - 1, str)
        str = str[:-1]
    return


combinations(left=total/2, right=total/2, toClose=0, str="")

print(combs)
remybroun commented on 02/18/20
Log in to submit a comment.
© 2025 Coderbyte