Generate Parentheses

Problem

Given an integer n, return every string made of exactly n opening and n closing parentheses that is well-formed, meaning every closing bracket matches an earlier unmatched opening one. Output order does not matter.

• n is between 1 and 9 pairs.

Examples

• n = 3 → ["((()))","(()())","(())()","()(())","()()()"]. Five strings; "())(()" is excluded because the third character closes with nothing open.
• n = 1 → ["()"].
• n = 2 → ["(())","()()"].

Hints

1. Build the string left to right. At any moment, what two counts fully describe whether the prefix can still be completed?
2. You may add ( as long as you have some left; you may add ) only if it would match an open bracket that is still unmatched.
3. Backtracking with open_used and close_used counters; add ) only when close_used < open_used.