CareerCup

public static void printBrackets(int left, int right, char[] str, int count)
	{
		if(left == 0 && right == 0)
			System.out.println(str);
		else
		{
			if(left > 0)
			{
				str[count] = '{';
				printBrackets(left -1, right, str, count + 1);
			}
			if(right > left)
			{
				str[count] = '}';
				printBrackets(left, right - 1, str, count + 1);
			}
		}
	}

for 2N braces, it can only be organized in two fashions:
(.....)(...) and (........)
In the first case, first ( and first ) meant to be a pair, second ( and second ) DOES NOT have to be a pair. so ()()() should be viewed as () ()()
In the second case, two ( ) is a pair, so ( ()() ) is valid, but not ()()()

In the first case, the first ')' can occur at i = 2, 4, .... 2N-2. For a fixed i, there are
f(i-2)*f(2n-i) cases
and for case two, f(2n-2) cases.
So f(n) = sum_{i=2, 4, ... 2N-2} ( f(i-2)*f(2n-i) ) + f(2n-2)

More details at stackoverflow.com/questions/3172179/valid-permutation-of-parenthesis

awesome answer.how do you think like that.

def paren(n):
  if n == 1: return ['()']
  else:
    pnless1 = paren(n-1)
    pn = []
    for i in pnless1:
      pn.append('()'+i)
      pn.append(i+'()')
      pn.append('('+i+')')
    pn = pn[1:] # to avoid the repeated pattern
    return pn

The solution provided by Hello World is most optimum one. We go on recursivelya dding left and right brackets to form valid strings.

We can add left brackets as long as we have left brackets remaining with us.
We can add right brackets as long as the number of right brackets remaining is > number of left brackets remaining.
When the number of right brackets and left brackets is exhausted, print the string