Generate All Valid Combinations of Balanced Parentheses
Company: Disney
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Generate All Valid Combinations of Balanced Parentheses
Given an integer `n` representing the number of pairs of parentheses, generate **all distinct strings of well-formed (balanced) parentheses** using exactly `n` pairs.
A string is well-formed if every opening parenthesis `(` has a matching closing parenthesis `)` and the parentheses are properly nested — equivalently, scanning left to right the number of `)` never exceeds the number of `(`, and the totals are equal at the end.
Return the list of all such strings. The order of the strings in the output does not matter.
### Examples
**Example 1**
```
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
```
**Example 2**
```
Input: n = 1
Output: ["()"]
```
**Example 3**
```
Input: n = 0
Output: [""]
```
### Constraints
- `0 <= n <= 8`
- Every string in the output uses exactly `n` opening and `n` closing parentheses.
- All strings in the output must be distinct and well-formed.
Quick Answer: This question tests a candidate's ability to apply recursive backtracking and combinatorial generation in a coding interview context. It evaluates understanding of constraint-based enumeration and string construction, core algorithmic skills frequently assessed in software engineering and data engineering roles.
Given an integer `n` representing the number of pairs of parentheses, generate **all distinct strings of well-formed (balanced) parentheses** using exactly `n` pairs.
A string is well-formed if every opening parenthesis `(` has a matching closing parenthesis `)` and the parentheses are properly nested — equivalently, scanning left to right the number of `)` never exceeds the number of `(`, and the totals are equal at the end.
Return the list of all such strings. The order of the strings in the output does not matter (this console compares against the lexicographically sorted list, so return your results sorted to match).
**Example 1:** `n = 3` → `["((()))", "(()())", "(())()", "()(())", "()()()"]`
**Example 2:** `n = 1` → `["()"]`
**Example 3:** `n = 0` → `[""]`
Constraints
- 0 <= n <= 8
- Every string in the output uses exactly n opening and n closing parentheses.
- All strings in the output must be distinct and well-formed.
- For n = 0 the output is a list containing the single empty string: [""].
Examples
Input: (3,)
Expected Output: ['((()))', '(()())', '(())()', '()(())', '()()()']
Explanation: n = 3: there are Catalan(3) = 5 well-formed strings, shown in lexicographic order.
Input: (1,)
Expected Output: ['()']
Explanation: n = 1: the only balanced string is '()'.
Hints
- Build strings character by character with backtracking. Track how many '(' and ')' you have placed so far.
- You may add a '(' as long as you have used fewer than n opening brackets. You may add a ')' only when the count of ')' placed is strictly less than the count of '(' placed — this keeps every prefix valid.
- Stop and record the string once its length reaches 2n. Return the collected strings sorted so the output ordering is deterministic.