Print all combinations of n balanced parentheses

Problem

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

Example
Input     3 (i.e., 3 pairs of parentheses)
Output    ()()(), ()(()), (())(), ((()))

Solution

This is a classic combinatorial problem that manifests itself in many different ways. Such kind of strings are called Dyck strings (see more here), which contain n X's and n Y's such that no initial segment of the string has more Y's than X's. example:
XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY

These problems are essentially identical:

• Generating all possible ways to balance N pairs of parentheses (i.e. this problem)
• Generating all possible ways to apply a binary operator to N+1 factors
• Generating all full binary trees with N+1 leaves
• Many others...

Such problems can be solved by recursion, backtracking, dynamic programming.


Method 1 - Recursion
We have to keep track of open and close parentheses. So we track how many open and close parentheses are "on stock" for us to use as we're building the string recursively.

• If there's nothing on stock, the string is fully built and you can just print it out
• If there's an open parentheses available on stock, try and add it on.
  • Now you have one less open parentheses, but one more close parentheses to balance it out
• If there's a close parentheses available on stock, try and add it on.
  • Now you have one less close parentheses

Code : 

    static void printAllParenthesesCombination(int openStock, int closeStock, String s) {
        if (openStock == 0 && closeStock == 0) {
            System.out.println(s);
        }
        if (openStock > 0) {
            printAllParenthesesCombination(openStock-1, closeStock+1, s + "(");
        }
        if (closeStock > 0) {
            printAllParenthesesCombination(openStock, closeStock-1, s + ")");
        }
    }
    public static void main(String[] args) {
        brackets(3, 0, "");
    }

Method 2 - Dynamic programming
Lets start with the base case

• base case , i.e. n =1
  if N == 1,
  output : ( )
  
• Now for N == 2, we have one more pair of braces. So we will use intuition of adding “(” at the front always(coz for being properly valid the first bracket has to be opening bracket. It’s a must). And then we add “)” at all the indices.
  
  Let’s simulate it here,
  
  

  we have String str = "( )" ;
  
  for(int i = 0; i < str.length(); i++)
  String ans = "("  +  str.substring(0, i) + ")" + str.substring(i);
  
  // the closing brace is used at all the possible positions around the given String ans.
  Thus, for i = 0, ans = "( ) ( )"
  for i = 1, and = "( ( ) )"
  

  
  That’s it. Given String is of length two only. So, lets go for general n
• Now for N == n

private static Set<String> set = new HashSet<String>();

public static void printAllParenthesisCombination(int s, int n, String str) {
    if (s == n) {
        set.add(str);
        return;
    }
    if (set.contains(str))
       return;
    for (int i = 0; i < str.length(); i++) {
       String ok = "("+ str.substring(0, i) + ")" + str.substring(i);
       printAllParenthesisCombination(s + 1, n, ok);
    }
}

//Calling method : 
printAllParenthesisCombination(1, n, "()")

In the above code I have used Set, because different parentheses may sometimes lead to same parentheses after insertion of "("‘ and ")". Thus instead of repeatedly calling it, I am prefering memoisation.

See also - http://en.wikipedia.org/wiki/Catalan_number, and good articles by Eric Lipert here and here.

References

• http://algoriddles.wordpress.com/2012/02/14/total-valid-n-pair-parentheses/
• http://tianrunhe.wordpress.com/2012/03/26/all-valid-combinations-of-n-pairs-of-parentheses/
• http://stackoverflow.com/questions/3172179/valid-permutation-of-parentheses
• http://en.wikipedia.org/wiki/Catalan_number 

Thanks