Lab 08 — Recursion & Stack: Generate Parentheses

Goal

Master backtracking with partial-state validity, the recursion tree as a mental model, the bound on recursion depth, and the Catalan-number cost analysis. The deliverable: enumerate all well-formed parenthesizations of N pairs and explain why the count is C_n (the n-th Catalan number).

Background Concepts

Recursion as a tree of choices; partial-state pruning vs full-state validation; recursion depth = call-stack frames; iterative backtracking as an explicit-stack alternative. Review runtime concept 10 (recursion depth) in the Phase 1 README and the Stacks section.

Interview Context

Generate Parentheses is asked at Google, Microsoft, Meta. The signal: do you generate only valid prefixes (prune early) instead of generating all 2^(2n) strings and filtering? Do you know the Catalan-number complexity? Can you also produce an iterative version using an explicit stack?

Problem Statement

Given an integer n, return all combinations of well-formed parentheses using exactly n pairs of ( and ).

Constraints

1 ≤ n ≤ 8 — the count grows as C_n = (2n)! / ((n+1)! n!). C_8 = 1430.
Output order is not specified; any valid enumeration is acceptable.

Clarifying Questions

Should output be sorted? (Usually no — but lexicographic falls out naturally if we always try ( before ).)
Is duplication possible? (No — each generated string is unique by construction.)
Should we return a list or stream the results? (List is canonical; streaming/yield is a follow-up.)
Empty case n = 0? (Per constraints n ≥ 1. If allowed: return [""].)
Are the parentheses always ( and )? (Yes for the canonical problem; brackets and braces is a generalization.)

Examples

`n`	Output
1	`["()"]`
2	`["(())", "()()"]`
3	`["((()))", "(()())", "(())()", "()(())", "()()()"]`
4	14 strings

Initial Brute Force

Generate all 2^(2n) strings of length 2n over {(, )}. Filter by validity (use the stack from Lab 05). Return the survivors.

def gen_brute(n):
    out = []
    def rec(s):
        if len(s) == 2*n:
            if is_valid(s):  # Lab 05 routine
                out.append(s)
            return
        rec(s + "(")
        rec(s + ")")
    rec("")
    return out

Brute Force Complexity

2^(2n) strings; each takes O(n) to validate. Total O(n · 4^n). For n = 8: ~10⁵ operations — fast, but for n = 16 it would be billions.

Optimization Path

Prune as we build. Track (open, close) counts; the rules are:

We may add ( if open < n.
We may add ) if close < open (otherwise we’d close before opening).

Every leaf of this pruned tree is a valid string; no validation needed. The number of leaves is exactly C_n.

Final Expected Approach

def generate_parentheses(n):
    out = []
    def backtrack(s, opens, closes):
        if len(s) == 2 * n:
            out.append(s)
            return
        if opens < n:
            backtrack(s + "(", opens + 1, closes)
        if closes < opens:
            backtrack(s + ")", opens, closes + 1)
    backtrack("", 0, 0)
    return out

Data Structures Used

The recursion call stack (depth = 2n).
An accumulator string built up by concatenation (or, for efficiency, a list of chars joined at the leaf).
An output list of strings.

Correctness Argument

Soundness: every leaf has length 2n, opens == n, closes == n (else we wouldn’t reach length 2n under the pruning rules). At every prefix, closes ≤ opens (we only added ) when closes < opens). Therefore every leaf is balanced.

Completeness: any valid parenthesization satisfies the same two rules at every prefix (it’s the characterization of valid prefixes). Therefore the recursion explores it. By induction on length: every valid prefix s of length < 2n extended by ( (if extensible) or ) (if extensible) appears in the tree.

Uniqueness: at each node we make distinct choices (( vs )), so two leaves cannot have the same string.

Complexity

Number of leaves: C_n = (2n)! / ((n+1)! n!) ≈ 4^n / (n^(3/2) · √π).
Cost per leaf: O(n) to copy the final string.
Total time: O(n · C_n) = O(4^n / √n).
Space: output is O(n · C_n). Recursion stack is O(n).

Implementation Requirements

Two counters: opens, closes. Don’t track the full prefix’s validity — the counters are sufficient.
Termination at len(s) == 2 * n, not when both counters hit n (equivalent, but the length check is clearer).
Pass s immutably (string concat) for clarity, or mutate a list and append/pop for performance — but for n ≤ 8 the difference is negligible.
Don’t generate then filter. The whole point is to not visit invalid branches.

Tests

Smoke: n = 3 → 5 strings.
Unit: n = 1 → ["()"]; n = 2 → 2 strings.
Edge: n = 0 (if allowed) → [""].
Property: count of returned strings equals C_n (compute reference Catalan number).
Property: every string in the output is valid (run Lab 05’s is_valid).
Property: all strings are distinct (length = len(set(out))).
Large: n = 8 returns 1430 strings in milliseconds.

Follow-up Questions

“Generate iteratively using an explicit stack.” → push partial states (s, opens, closes); pop and expand.
“Return only the count, not the strings.” → that’s just C_n; closed form: comb(2n, n) // (n + 1).
“Brackets, braces, and parens (multi-type).” → much harder; can’t be solved by simple counters because the closer must match the most-recent opener.
“Stream results lazily (generator/yield).” → in Python, yield from each leaf; saves memory.
“Memoize.” → the canonical formulation has no overlapping subproblems on (opens, closes, s) because s is unique at every state. If you parametrize by just counts, you lose the actual string.
“Why is the count C_n?” → bijection with Dyck paths, balanced trees of n+1 leaves, etc.

Product Extension

A SQL/expression-grammar generator for fuzz testing. Generating syntactically valid parenthesized expressions is a backtracking-with-pruning problem; arbitrary depth-bounded grammars use the same technique. The code-generation engine inside any compiler’s “synthesize a small valid program” tool uses this exact pattern.

Language/Runtime Follow-ups

Python: strings are immutable, so each s + "(" allocates. For larger n, build with a list and "".join(...) at the leaf.
Java: use StringBuilder and delete/setLength at backtrack — the canonical mutable-builder pattern. Pass the builder by reference; remember to undo each append on return.
Go: strings are immutable; use []byte or strings.Builder. Beware: a strings.Builder does not support truncation; use a byte slice with a manual length pointer.
C++: use std::string mutated in place with push_back / pop_back. Pass by reference.
JS/TS: strings are immutable; concat is fine for small n. For larger, use an array.
Recursion depth: 2n. For n ≤ 8, depth ≤ 16 — trivial. Even n = 1000 (academic) is safe in most languages.
Tail-call optimization: absent in Python and JS; this code isn’t tail-recursive anyway because there are two recursive branches.

Common Bugs

Adding ) without checking closes < opens — generates )(... prefixes that can never become valid; produces duplicates and invalid strings.
Adding ( without checking opens < n — overshoots; never closes; never reaches the leaf condition.
Wrong termination — if opens == n and closes == n instead of if len(s) == 2n is fine but harder to reason about.
Backtracking with mutation but not undoing — append (, recurse, forget to pop before recursing again. Adds spurious chars.
Catalan miscount — saying complexity is O(2^(2n)) instead of O(4^n / √n) is a forgivable but suboptimal answer.

Debugging Strategy

Print the recursion tree: indent by len(s) and show (s, opens, closes).
Run for n = 2 and verify the output is exactly ["(())", "()()"].
Count outputs and compare to comb(2n, n) // (n + 1).

Mastery Criteria

Identified backtracking-with-pruning as the right tool within 60 seconds.
Wrote the two pruning rules without help.
Stated complexity as O(n · C_n) ≈ O(4^n / √n).
Acknowledged the Catalan-number connection.
Wrote the iterative-with-explicit-stack version on demand.
Selected the appropriate language idiom (StringBuilder, []byte, etc.) and remembered to undo mutations on backtrack.

LeetCode Interview — Extreme Coding