Generate Parentheses

Given an integer n, generate every distinct string that contains exactly n left parentheses ( and n right parentheses ) and is a valid well-formed parentheses sequence.

A parentheses string is valid if:

• Every prefix has at least as many ( as ).
• The total number of ( equals the total number of ).

Return all valid combinations in any order.

Input Format

• A single integer n.

Output Format

• Return a list of strings, where each string is a valid parentheses sequence using exactly n pairs.

Constraints

• $1 \le n$ is typically small enough for exhaustive generation.
• The number of valid results grows combinatorially with n.

Hints

• Build the string one character at a time.
• Never add a right parenthesis unless there are more unmatched left parentheses available.
• Stop when the current string reaches length $2n$.