The Parentheses Factory

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

A template engine checks its output by enumerating every legal bracket nesting it could emit. Given a non-negative integer n, return every well-formed string built from n pairs of parentheses, including the empty string when n is 0. Order the results so that, comparing them character by character, an open paren ranks before a close paren.

Building balanced brackets is an art form.

Example 1

Input:

n = 3

Output:

["((()))","(()())","(())()","()(())","()()()"]

Example 2

Input:

n = 1

Output:

["()"]

Worked solution and explanation

What this really is

Strip the costume off and this is a constrained string-enumeration problem: you are walking the tree of all open/close sequences and refusing to descend any branch that can never close cleanly. Anyone can generate every length-2n string and filter; the people who pass build only the valid ones by enforcing two invariants as they go. Get the close condition wrong and you emit ())( and friends, or you silently drop half the answers.

Walking the decision tree

Step 1: Start from nothing

An empty string with both counters at zero. Every recursive call appends exactly one character, so the depth of the recursion is the length of the string so far.

Step 2: Spend an open paren when you have one

If open_count < n you still have opens left to spend, so recurse with ( appended and open_count bumped. Trying this branch first is what produces the open-before-close ordering the prompt asks for: deeper-nested strings come out ahead of flatter ones.

Step 3: Close only what is already open

Only when close_count < open_count is there an unmatched ( sitting to the left waiting to be closed. This is the guard that keeps every prefix valid; without it you generate garbage like )(.

Step 4: Collect at the leaf

When the string hits length 2n, both counters have reached n and the string is guaranteed balanced, so record it and return. No final validity check is needed because you never built an invalid prefix.

The solution

Pruned recursion over open/close counts
def generate_parentheses(n: int) -> list:
    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

Trying the open branch before the close branch yields ascending order with '(' ranked before ')'.

Common follow-up questions