# Proper Bracket Sequences

Problem #140

Tags: puzzle dynamic-programming strings

Who solved this?

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:

• amounts of opening and closing brackets are equal;
• for any "prefix" (i.e. substring starting from the beginning of the string) amount of opening brackets is greater or equal to amount of closing ones.

So for example:

``````(()(()(())))     - correct sequence
)()()(           - not correct, substring(0, 1) contains 1 closing brackets and no opening
()(()(())        - not correct, one extra opening bracket.
``````

### Problem Statement

For given `N` you are to tell how many correct bracket strings of length `2N` could be built.

Here is only one variant for `N=1`:

``````()
``````

Two variants for `N=2`:

``````(())    ()()
``````

Five for `N=3`:

``````((()))  (())()  ()(())  (()())  ()()()
``````

And so on.

Input data contain a single value `N`, not exceeding `400`.
Answer should contain exact (though perhaps pretty long) number of variants.

Example:

``````input data:
10