Interview Questions

  • View all algorithm tutorials
  • blank
  • Generate all balanced bracket combinations

    Want more content about improving your career, algorithms, and interview practice? Check out our newsletter!

    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; 
    
    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 
    
    Run Code
    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...
    mrdaniel published this on 2/8/16 | math, Google
    Comments
  • +
  • 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.
  • +
  • 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.
    Log in to submit a comment.