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

We can solve this problem recursively by recursing through the string. On each iteration, we
have the index for a particular character in the string. We need to select either a left or a right
paren. When can we use left, and when can we use a right paren?
»»    Left: As long as we haven’t used up all the left parentheses, we can always insert a left
      paren.
»»    Right: We can insert a right paren as long as it won’t lead to a syntax error. When will we
      get a syntax error? We will get a syntax error if there are more right parentheses than
      left.
So, we simply keep track of the number of left and right parentheses allowed. If there are left parens remaining, we’ll insert a left paren and recurse. If there are more right parens remaining than left (eg, if there are more left parens used), then we’ll insert a right paren and recurse.

1        public static void printPar(int l, int r, char[] str, int count) {
2                 if (l < 0 || r < l) return; // invalid state
3                 if (l == 0 && r == 0) {
4                         System.out.println(str); // found one, so print it
5                 } else {
6                         if (l > 0) { // try a left paren, if there are some available
7                                str[count] = ‘(‘;
8                                printPar(l - 1, r, str, count + 1);
9                         }
10                        if (r > l) { // try a right paren, if there’s a matching left
11                               str[count] = ‘)’;
12                               printPar(l, r - 1, str, count + 1);
13                        }
14                }   
15       }
16          
17       public static void printPar(int count) {
18                char[] str = new char[count*2];
19                printPar(count, count, str, 0);
20       }