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
<[email protected]>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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
