Proper Bracket Sequences
This problem was brought to me by some colleague at forum - he got it at interview for position of Ruby-on-Rails web-developer and was somewhat confused.
You probably remember Matching Brackets task. This one is also about brackets but of a single kind - let them be round brackets.
The string of brackets is correct if the following conditions hold:
So for example:
(()(()(()))) - correct sequence )()()( - not correct, substring(0, 1) contains 1 closing brackets and no opening ()(()(()) - not correct, one extra opening bracket.
N you are to tell how many correct bracket strings of length
2N could be built.
Here is only one variant for
Two variants for
((())) (())() ()(()) (()()) ()()()
And so on.
Input data contain a single value
N, not exceeding
Answer should contain exact (though perhaps pretty long) number of variants.
input data: 10 answer: 16796