Generate Parentheses

Given n pairs of parentheses, return every distinct well-formed string containing exactly n opening and n closing parentheses. A prefix must never contain…

Given n pairs of parentheses, return every distinct well-formed string containing exactly n opening and n closing parentheses. A prefix must never contain more closing than opening parentheses. Return all valid strings exactly once, in any order.

- 1 <= n <= 8. - Each returned string has exactly 2 * n characters, all '(' or ')'. - Return every valid string exactly once; output order does not matter.

Example 1: input n = 1; output ["()"]. The only balanced string uses one opening parenthesis followed by its matching close.

Example 2: input n = 2; output ["(())","()()"]. The two pairs may be nested or adjacent. Strings beginning with a close are invalid.

Example 3: input n = 3; output ["((()))","(()())","(())()","()(())","()()()"]. These five strings use all three pairs and keep every prefix balanced.

Category: Recursion. Topic: recursion. Difficulty: Medium. Patterns: backtracking.