Generate Parentheses¶

Problem¶

Given n pairs of parentheses, generate all combinations of well-formed (balanced) parentheses.

Approach¶

Backtracking: maintain counts of open and close parens placed so far. Add '(' if open < n. Add ')' if close < open. Base case: length == 2*n.

When to Use¶

Generating all valid structures (expressions, trees, paths). Classic backtracking with pruning. Output count follows Catalan numbers.

Complexity¶


Time	`O(4^n / sqrt(n)) — nth Catalan number`
Space	`O(n) — recursion depth (excluding output)`

Implementation¶

SolutionTestsChallenge

generate_parentheses ¶

Generate Parentheses — all valid combinations of n pairs.

Problem

Given n pairs of parentheses, generate all combinations of well-formed (balanced) parentheses.

Approach

Backtracking: maintain counts of open and close parens placed so far. Add '(' if open < n. Add ')' if close < open. Base case: length == 2*n.

When to use

Generating all valid structures (expressions, trees, paths). Classic backtracking with pruning. Output count follows Catalan numbers.

Complexity

Time: O(4^n / sqrt(n)) — nth Catalan number Space: O(n) — recursion depth (excluding output)

generate_parentheses ¶

generate_parentheses(n: int) -> list[str]

Return all valid combinations of n pairs of parentheses.

generate_parentheses(1) ['()'] sorted(generate_parentheses(2)) ['(())', '()()']

Source code in src/algo/recursion/generate_parentheses.py

def generate_parentheses(n: int) -> list[str]:
    """Return all valid combinations of *n* pairs of parentheses.

    >>> generate_parentheses(1)
    ['()']
    >>> sorted(generate_parentheses(2))
    ['(())', '()()']
    """
    result: list[str] = []

    def backtrack(current: list[str], open_count: int, close_count: int) -> None:
        if len(current) == 2 * n:
            result.append("".join(current))
            return
        if open_count < n:
            current.append("(")
            backtrack(current, open_count + 1, close_count)
            current.pop()
        if close_count < open_count:
            current.append(")")
            backtrack(current, open_count, close_count + 1)
            current.pop()

    if n > 0:
        backtrack([], 0, 0)
    return result

tests/recursion/test_generate_parentheses.py

"""Tests for the generate parentheses problem."""

from hypothesis import given
from hypothesis import strategies as st

from algo.recursion.generate_parentheses import generate_parentheses


def _is_valid_parentheses(s: str) -> bool:
    """Check if a parentheses string is balanced."""
    balance = 0
    for ch in s:
        if ch == "(":
            balance += 1
        else:
            balance -= 1
        if balance < 0:
            return False
    return balance == 0


# Catalan numbers for n = 0..6
_CATALAN = [1, 1, 2, 5, 14, 42, 132]


class TestGenerateParentheses:
    def test_one_pair(self) -> None:
        assert generate_parentheses(1) == ["()"]

    def test_two_pairs(self) -> None:
        assert sorted(generate_parentheses(2)) == ["(())", "()()"]

    def test_three_pairs(self) -> None:
        result = sorted(generate_parentheses(3))
        assert result == ["((()))", "(()())", "(())()", "()(())", "()()()"]

    def test_zero_pairs(self) -> None:
        assert generate_parentheses(0) == []

    def test_count_matches_catalan(self) -> None:
        for n in range(1, 6):
            assert len(generate_parentheses(n)) == _CATALAN[n]

    @given(n=st.integers(min_value=1, max_value=5))
    def test_all_results_are_valid(self, n: int) -> None:
        results = generate_parentheses(n)
        for s in results:
            assert len(s) == 2 * n
            assert _is_valid_parentheses(s)
        # No duplicates
        assert len(results) == len(set(results))

Implement it yourself

Run: just challenge recursion generate_parentheses

Then implement the functions to make all tests pass. Use just study recursion for watch mode.

Reveal Solution

generate_parentheses ¶

Generate Parentheses — all valid combinations of n pairs.

Problem

Given n pairs of parentheses, generate all combinations of well-formed (balanced) parentheses.

Approach

Backtracking: maintain counts of open and close parens placed so far. Add '(' if open < n. Add ')' if close < open. Base case: length == 2*n.

When to use

Generating all valid structures (expressions, trees, paths). Classic backtracking with pruning. Output count follows Catalan numbers.

Complexity

Time: O(4^n / sqrt(n)) — nth Catalan number Space: O(n) — recursion depth (excluding output)

generate_parentheses ¶

generate_parentheses(n: int) -> list[str]

Return all valid combinations of n pairs of parentheses.

generate_parentheses(1) ['()'] sorted(generate_parentheses(2)) ['(())', '()()']

Source code in src/algo/recursion/generate_parentheses.py

def generate_parentheses(n: int) -> list[str]:
    """Return all valid combinations of *n* pairs of parentheses.

    >>> generate_parentheses(1)
    ['()']
    >>> sorted(generate_parentheses(2))
    ['(())', '()()']
    """
    result: list[str] = []

    def backtrack(current: list[str], open_count: int, close_count: int) -> None:
        if len(current) == 2 * n:
            result.append("".join(current))
            return
        if open_count < n:
            current.append("(")
            backtrack(current, open_count + 1, close_count)
            current.pop()
        if close_count < open_count:
            current.append(")")
            backtrack(current, open_count, close_count + 1)
            current.pop()

    if n > 0:
        backtrack([], 0, 0)
    return result