A gift-wrapping machine forms ribbon loops encoded as strings of ( and ). A string is balanced if it uses exactly n opening brackets and n closing brackets, and in every prefix the number of opening brackets is at least the number of closing brackets.
Count how many distinct balanced strings use exactly n pairs of brackets.
A single line: the integer n.
A single integer: the number of balanced bracket strings with exactly n pairs.
Example 1
Input
3
Expected
5
Explanation
The five balanced strings are ((())), (()()), (())(), ()(()), and ()()().
Example 2
Input
1
Expected
1
Explanation
The only balanced string with one pair is ().
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →