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 → ["((()))","(()())","(())()","()(())","()()()"]

Expected approach

• Backtracking with two counters: append '(' while open < n; append ')' while close < open; emit at length 2n. The invariant close <= open <= n guarantees validity by construction — no post-filtering. O(Catalan(n) * n). Be ready to state why brute-forcing all 2^(2n) strings and validating is wasteful, and to connect the count to Catalan numbers.