content: package backtracks;
  
  import java.util.ArrayList;
  import java.util.List;
  
  public class Parenthesis {
  
  
      /*
       * Print all parentheses combinations for a given value n such that they are balanced.
       * Input: 3
       * Output: {{{}}}
       *         {{}{}}
       *         {{}}{}
       *         {}{{}}
       *         {}{}{}
       *
       * Runtime Complexity:
       * Exponential
       *
       * Memory Complexity:
       * Linear, O(n)
       *
       *
       * The solution is to maintain counts of left and right parentheses.
       * left parentheses count: 0
       * right parentheses count: 0
       *
       * if left parentheses count is less than n:
       *      add left parentheses and recurse further
       *
       * if right parentheses count is less than left parentheses count:
       *      add right parentheses and recurse further
       *
       * stop recursing when left and right counts are both equal to n
       *
       * */
  
      static void printList(List<Character> l) {
          for (Character c : l) {
              System.out.print(c);
          }
          System.out.println();
      }
  
      static void printAllParenthesesRec(int n,
                                         int left_count,
                                         int right_count,
                                         List<Character> output) {
  
          if (left_count >= n && right_count >=n) {
              printList(output);
          }
  
          if (left_count < n) {
              output.add('{');
              printAllParenthesesRec(
                      n, left_count + 1, right_count, output);
              output.remove(output.size() - 1);
          }
  
          if (right_count < left_count) {
              output.add('}');
              printAllParenthesesRec(
                      n, left_count, right_count + 1, output);
              output.remove(output.size() - 1);
          }
      }
  
      static void printAllParentheses(int n) {
          List<Character> output = new ArrayList<>();
          printAllParenthesesRec(n, 0, 0, output);
      }
  
  
      public static void main(String[] args) {
          printAllParentheses(3);
      }
  }
  