Print all combinations of balanced parentheses

Problem: Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n pairs of parentheses.

In this problem, we are given n open (‘{’)and closed(‘}’) brackets. We have to print all the possible combinations of them to be balanced. Balanced parentheses mean that for every open bracket there is a closed bracket. For example , if n = 2

Balanced :

{}{} , {{}}

Unbalanced :

}}{{ , {}}{ , }{}{

We can deduce that we will have to use a recursive function in which we can add an opening and closing bracket with the condition that it is a balanced one. So how do we think of such a recursive function? Let’s say that we are given an empty string. In the first iteration, this string has 2 choices — either to add an opening bracket or add a closing bracket.

F (“”,n) = F(“{”,n-1) + F(“}”,n-1)

Though in the above equation the second part is invalid and we need to make a condition that we stop propagating the second function call. Our base calls will be when there are no more opening or closing brackets to be put.

There are two approaches that are almost similar to solve this problem. The first approach takes the character array of length 2n to store n open and closed brackets. It then makes a choice to place either an open or closed bracket on the current index.

The second approach takes the empty String and appends the open bracket in one function call while appending the closed bracket in another function call. Time complexity and space complexity are the same for both but added work of appending bracket in a string makes the second approach add an extra constant in time complexity.

public class Parens{
static void _printParenthesisCharacterArray(char[] str , int current , int n , int open , int closed){
  if(closed == n){
   for(char c : str){
     System.out.print(c);
   }
   System.out.println();
 }else{
  if(open < n){
   str[current] =’{‘;
   _printParenthesisCharacterArray(str,current+1,n,open+1,closed);
  }
  if(closed < open){
   str[current] = ‘}’;
   _printParenthesisCharacterArray(str,current+1,n,open,closed+1);
  }
 }
}
static void printParenthesisCharacterArray(char[] str,int n){
 _printParenthesisCharacterArray(str,0,n,0,0);
}
static void printParenthesisEmptyString(int n){
 _printParenthesisEmptyString(“”,n,n,n);
}
static void _printParenthesisEmptyString(String str , int n , int openParens , int closeParens){
 if(openParens < 0 || closeParens < 0){
  return;
 }
 if(closeParens == 0){
  System.out.println(str);
 }
 if(openParens > 0){
  _printParenthesisEmptyString(str + “{“,n,openParens-   1,closeParens);
 }
if(closeParens > openParens){
  _printParenthesisEmptyString(str + “}”,n,openParens,closeParens-1);
 }
 }
public static void main(String[] args) {
 
 int n = 3;
 char[] str = new char[2 * n];
 
 System.out.println(“Method with character array”);
 printParenthesisCharacterArray(str, n);
 System.out.println(“Method with empty String”);
 printParenthesisEmptyString(n);
 }
}

Time Complexity = O(2^n) because in each call there are 2 branches coming out which then go on making the other 2 calls. This will go to 2n length. Thus, 2^(2n) i.e O(2^n)

Space Complexity = O(n) because the character array will hold at max 2n elements while function calls will stack up to 2n at once. Thus it will be O(2n) i.e O(n).