# The Parentheses Factory

> Building balanced brackets is an art form.

Canonical URL: <https://datadriven.io/problems/the_parentheses_factory>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given non-negative integer n, return all well-formed strings of n pairs of parentheses. Return the list sorted in any deterministic order (test expects the same order as the standard backtracking algorithm).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **backtracking with pruning constraints**. Generating valid parentheses requires understanding that at any point, the number of open brackets must be at least the number of closed ones, and neither can exceed n.

> **Trick to Solving**
>
> Use two counters: `open_count` and `close_count`. You can add `(` if `open_count < n`. You can add `)` only if `close_count < open_count`. This pruning eliminates invalid combinations without generating and filtering.

---

### Break down the requirements

#### Step 1: Start with an empty string and both counters at 0

The recursion builds the string one character at a time.

#### Step 2: Add an open paren if open_count is less than n

This ensures we do not exceed n pairs total.

#### Step 3: Add a close paren if close_count is less than open_count

This ensures every close has a matching open before it.

#### Step 4: Collect the string when its length reaches 2n

At this point, all n pairs are placed and the string is valid.

---

### The solution

**Backtracking with open/close count pruning**

```python
def generate_parens(n):
    result = []
    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)
    backtrack('', 0, 0)
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(4^n / sqrt(n)), the nth Catalan number. This is the number of valid combinations.
> 
> **Space:** O(n) for the recursion depth, plus O(C_n * 2n) for storing all results.

> **Interviewers Watch For**
>
> Can you explain why `close_count < open_count` is the right condition? It ensures every `)` has a corresponding unmatched `(` to its left, maintaining validity at every step.

> **Common Pitfall**
>
> Generating all 2^(2n) binary strings and filtering valid ones. This is exponentially slower than pruned backtracking and signals a lack of algorithmic sophistication.

---

## Common follow-up questions

- How would you generate only the kth valid combination? _(Tests ranking/unranking Catalan number sequences.)_
- What if you also had square and curly brackets? _(Tests extending the backtracking to multiple bracket types with nesting rules.)_
- How does the count of valid combinations relate to Catalan numbers? _(Tests mathematical knowledge: C(n) = (2n)! / ((n+1)! * n!).)_
- What if you needed to generate them iteratively instead of recursively? _(Tests converting recursion to a stack-based approach.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_parentheses_factory)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.