permutation of parantheses

problem : generate all the permutations of valid parantheses

e.g.

input 1
output {}

input 2
output {}{}, {{}}

input 3
output: {}{}{}, {{{}}}, {{}{}}, {{}}{}, {}{{}}

solution :

note : number of permutation can be easily found by noticing that it is forming a catalan series, 1,2,5,... so nth term will be (2^n -n).

solution: