Generate Parentheses

Problem Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Input / Output

• Input: int n. Output: all valid strings of n '(' and n ')'.

Constraints

• 1 <= n <= 8; output size is the nth Catalan number — exponential by nature.

Example

• n = 3 → ["((()))","(()())","(())()","()(())","()()()"]