All Balanced Bracket Strings

A string of round brackets is balanced when every ( is closed by a later ) and no ) closes something that was never opened. Write balanced_strings(n) that returns every balanced string made of exactly n opening and n closing brackets, as a sorted list.

Examples

balanced_strings(1)  # returns ['()']
balanced_strings(2)  # returns ['(())', '()()']
balanced_strings(3)  # returns ['((()))', '(()())', '(())()', '()(())', '()()()']

Constraints

• 0 <= n <= 10

Note

For n = 0 there is exactly one balanced string, the empty string, so the answer is ['']. The count grows fast: there are 16,796 strings for n = 10.