OJ Board

I have the following problem.

From a given number N <= 100, where N is the length of the string, i need to find K, where K is the number of correct strings.

Strings consists of round bracket expressions. Every position in string can assume either "(" or ")".

Correct round bracket expression looks like this - "()". If A is correct round bracket expression, then "(A)" is correct expression too. If A and B are correct expression then "AB" is correct too.

For example, if N=4, there are 2 correct strings - "()()" and "(())", if N=6, then there are 5 correct strings - "((()))", "()(())", "(())()", "()()()", "(()())". Incorrect strings for N=4 looks like this - ")()(", ")()(", "))))", "((((", etc.

Could somone advise efficient way how to solve this problem ?
Thanks.

P.S.
My current solution solves this problem efficient (in 2 or less seconds) only if N<= 22. I'm using a little modified backtracking algorithm.

Search for Catalan Numbers.

Your backtracking algorithm will also run in time if you memoize previously calculated values ([position in string][nesting depth]), 101*51 states should suffice.

Hi!

the set of all boolean vectors of length n (n is even) that enjoy the following property:
1) for every initial fragment (0...k, k<n) number of 1's >= number of 0's
2)number of 1's == number of 0's in total.

is isomorphic (in some ordinary sense of this extraordinary word )
to the set you're studying.

Good luck!