A recursive way of filling each position is better, so we can cut it down when its invalid and not proceed further. Something like below,
// 1-based indexing -> global n , A[2*n+1] -> go( ci , cs ) // cur.index , cur.sum { if( ci == 2n+1 ) print A with [ 1 = '(', -1 = ')' ] toFill = 2*n - ci + 1; if( cs < toFill ) { A[ci] = 1; go( ci+1 , cs+1 ); } if( cs > 0 ) { A[ci] = -1; go( ci+1 , cs-1 ); } } -> in main A[1] = 1; go(2,1); -- AK On Thu, Jun 3, 2010 at 1:45 PM, Jitendra Kushwaha <jitendra.th...@gmail.com>wrote: > The question is that you have to print all the valid permutations of > the given number of brackets > for example for input 3 we have the output > > 1 ((())) > 2 (()()) > 3 (())() > 4 ()(()) > 5 ()()() > > total five valid permutation > > this can be solved in O( 2^(2n) ) where n is number of brackets . > Algo will be like this > 1. Try '(' and ')' in every position and print the correct > permutation.Neglect all other permutation > > As catalon number is far less then exponential growth ,can anybody > suggest some better algorithm > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Anil Kishore -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.