Generate Parentheses: List Every Balanced String of n Pairs

Problem

Given an integer n ≥ 0, return all distinct strings made of n opening and n closing parentheses that are balanced: every prefix has at least as many ( as ), and the totals are equal. Order of the result does not matter. This is widely known as LeetCode 22, Generate Parentheses.

Examples

n = 1   ->  ["()"]
n = 2   ->  ["(())", "()()"]
n = 3   ->  ["((()))", "(()())", "(())()", "()(())", "()()()"]
n = 0   ->  [""]

Approach 1: brute force

Generate all 2^(2n) strings of length 2n and keep the balanced ones.

from itertools import product

def balanced(s):
    depth = 0
    for ch in s:
        depth += 1 if ch == "(" else -1
        if depth < 0:
            return False
    return depth == 0

def generate_brute(n):
    return ["".join(p) for p in product("()", repeat=2 * n) if balanced("".join(p))]

Complexity: O(2^(2n) · n) time. Only usable for small n.

Approach 2: optimal (backtracking)

Key insight: never build a prefix that is already invalid. A prefix stays valid as long as openers used ≤ n and closers used ≤ openers used. With those two rules, every string that reaches length 2n is balanced, and no work is wasted on dead ends.

Walkthrough for n = 2 (o = openers used, c = closers used):

""        o=0 c=0  -> only "(" allowed
"("       o=1 c=0  -> "(" or ")"
"(("      o=2 c=0  -> only ")"      -> "(()" -> "(())"   done
"()"      o=1 c=1  -> only "("      -> "()(" -> "()()"   done

def generate_parentheses(n):
    result, path = [], []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Complexity: the output has C(n) = (2n)! / ((n + 1)! · n!) strings (the nth Catalan number), each of length 2n, so time and output space are O(C(n) · n). Recursion depth is 2n.

Tests

import math

def catalan(n):
    return math.comb(2 * n, n) // (n + 1)

for f in (generate_parentheses, generate_brute):
    assert f(1) == ["()"]
    assert sorted(f(2)) == ["(())", "()()"]
    assert sorted(f(3)) == ["((()))", "(()())", "(())()", "()(())", "()()()"]
    assert f(0) == [""]                                   # zero pairs

for n in range(0, 7):
    out = generate_parentheses(n)
    assert len(out) == len(set(out)) == catalan(n)        # distinct, right count
    assert all(balanced(s) for s in out)
    assert sorted(out) == sorted(generate_brute(n))

assert len(generate_parentheses(10)) == 16796             # larger n

Edge cases and pitfalls

• The closing rule is closed < opened, not closed < n; the latter produces strings like ")(".
• Building new strings (s + "(") in each call is simpler and fine for interview sizes; a shared list with append and pop avoids repeated copying.
• n = 0 should return [""] (one empty arrangement), not []. Confirm with the interviewer.

Where this shows up in data engineering

Rarely directly. Backtracking with pruning, extending a partial solution only while it can still be valid, is how constraint-based schedulers and query optimisers explore join orders without enumerating every permutation.