Generate All Well-Formed Parenthesis Strings
Company: Disney
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
A string of parentheses is called **well-formed** if every opening bracket `(` has a matching closing bracket `)` and the brackets are correctly nested. For example, `(())` and `()()` are well-formed, while `)(`, `(()`, and `())(` are not.
Given an integer `n`, generate **all** well-formed strings that use exactly `n` opening brackets and `n` closing brackets (so each string has length `2 * n`). Return them as a list. The order of the strings in the returned list does not matter, but every returned string must be distinct.
### Examples
**Example 1**
```
Input: n = 1
Output: ["()"]
```
**Example 2**
```
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
```
(Any ordering of these 5 strings is accepted.)
**Example 3**
```
Input: n = 0
Output: [""]
```
The only string using zero opening and zero closing brackets is the empty string, which is considered well-formed.
### Constraints
- `0 <= n <= 8`
- Every string in the output must be well-formed, must contain exactly `n` opening and `n` closing brackets, and must be unique.
- The number of valid strings grows as the Catalan number $C_n = \frac{1}{n+1}\binom{2n}{n}$ (e.g., $C_8 = 1430$), so the output can be large but is bounded.
Quick Answer: This question tests practical understanding of recursion and backtracking through enumeration of all valid parenthesis combinations of a given length. It is a classic coding interview problem that evaluates combinatorial reasoning, constraint-based pruning, and familiarity with Catalan number sequences in algorithm design.
A string of parentheses is called **well-formed** if every opening bracket `(` has a matching closing bracket `)` and the brackets are correctly nested. For example, `(())` and `()()` are well-formed, while `)(`, `(()`, and `())(` are not.
Given an integer `n`, generate **all** well-formed strings that use exactly `n` opening brackets and `n` closing brackets (so each string has length `2 * n`). Return them as a list. The order of the strings in the returned list does not matter, but every returned string must be distinct.
### Examples
**Example 1**
```
Input: n = 1
Output: ["()"]
```
**Example 2**
```
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
```
(Any ordering of these 5 strings is accepted.)
**Example 3**
```
Input: n = 0
Output: [""]
```
The only string using zero opening and zero closing brackets is the empty string, which is considered well-formed.
### Note on ordering
The grader compares against a canonical (sorted) ordering. The reference solutions sort the result before returning so the output is deterministic; in a real interview any ordering of the distinct well-formed strings is correct.
### Constraints
- `0 <= n <= 8`
- Every string in the output must be well-formed, must contain exactly `n` opening and `n` closing brackets, and must be unique.
- The number of valid strings grows as the Catalan number C_n = (1/(n+1)) * binomial(2n, n) (e.g., C_8 = 1430), so the output can be large but is bounded.
Constraints
- 0 <= n <= 8
- Every output string is well-formed and uses exactly n opening and n closing brackets
- All output strings are distinct
- Output length equals the n-th Catalan number C_n (C_8 = 1430)
Examples
Input: (1,)
Expected Output: ["()"]
Explanation: n=1: the only well-formed string of one pair is ().
Input: (0,)
Expected Output: [""]
Explanation: n=0: zero pairs, the single well-formed string is the empty string.
Input: (2,)
Expected Output: ["(())", "()()"]
Explanation: n=2: two well-formed strings — a nested pair (()) and two adjacent pairs ()().
Input: (3,)
Expected Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Explanation: n=3: C_3 = 5 distinct well-formed strings, shown in sorted order.
Input: (4,)
Expected Output: ["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]
Explanation: n=4: C_4 = 14 distinct well-formed strings in sorted order (boundary stress case).
Hints
- Build strings character by character with backtracking, tracking how many '(' and ')' you have placed.
- You may add a '(' only while the count of opened brackets is < n. You may add a ')' only while it would not exceed the number of '(' already placed (close < open).
- When the string reaches length 2*n it is guaranteed well-formed; record it. This naturally produces only valid, distinct strings — no need to filter.