Stack crash course ↗ · 19

22. Generate Parentheses

Build all valid parentheses combinations by backtracking: add ( while you still have opening brackets left, add ) only when it would not overtake the open count. This prunes the decision tree to only valid states.

● MediumBacktrackingRecursionTypeScript

PROBLEM What we're solving

Given a number n, return all combinations of n pairs of well-formed parentheses. For n=2 the answer is ["(())", "()()"]. For n=3 there are 5 valid strings: ["((()))", "(()())", "(())()", "()(())", "()()()"]. Order within the output does not matter.

KEY IDEA Two pruning rules keep only valid states

Insight → at any point in building the string, track open (how many ( placed) and close (how many ) placed). You may add ( whenever open < n, and ) whenever close < open. These two rules together guarantee every branch stays valid — no backtracking over invalid states, just construction of correct ones.

RECIPE Backtrack with two guards

0 · Start. Call backtrack('', 0, 0) — empty string, zero opens, zero closes.
1 · Base case. When cur.length === 2 * n, push to result and return. Every valid combination has exactly 2n characters.
2 · Add (. If open < n, recurse with open + 1. We still have opening brackets to spend.
3 · Add ). If close < open, recurse with close + 1. Closing only when there is an unmatched open prevents invalid states.

Classic confusion → people often try to validate at the end (generate all 2²ⁿ strings, filter) instead of pruning during construction. The two guards remove invalid prefixes eagerly: once you exceed n opens or let closes overtake opens, no valid string can follow, so you simply never go there.

COST Complexity & alternatives

Generate all, filter

O(n · 2²ⁿ)

2²ⁿ strings × length-n validation. Most strings are garbage.

Pruned backtracking

O(n · Cₙ)

Cₙ is the nth Catalan number ≈ 4ⁿ/n^3/2. Each of the Cₙ valid strings costs O(n) to build.

Space note

The recursion stack depth is 2n (max string length), so auxiliary space is O(n) excluding the output. The output itself is O(n · Cₙ) for the same reason.

Pattern transfer → the same "build and prune" structure appears in Combination Sum (budget guard), Permutations (used-set guard), Subsets (index guard), and N-Queens (column/diagonal guard). Any time you enumerate structures with local validity rules, reach for backtracking.

RUN IT Backtrack the decision tree: ( while open<n, ) while close<open

n =

step 0 / 18

STARTStart: n=2. Call backtrack('', 0, 0).

1▶function generateParenthesis(n: number): string[] {
2▶  const result: string[] = [];
3 
4  function backtrack(cur: string, open: number, close: number): void {
5    if (cur.length === 2 * n) {
6      result.push(cur);
7      return;
8    }
9    if (open < n) {
10      backtrack(cur + '(', open + 1, close);
11    }
12    if (close < open) {
13      backtrack(cur + ')', open, close + 1);
14    }
15  }
16 
17▶  backtrack('', 0, 0);
18  return result;
19}

_0_1_2_3

State

open

cur

depth

[]

result

just added (just added )recorded resultdone

slowfast

TYPESCRIPT The solution, annotated

generateParenthesis.ts
function generateParenthesis(n: number): string[] {
  const result: string[] = [];

  function backtrack(cur: string, open: number, close: number): void {
    if (cur.length === 2 * n) {
      result.push(cur);
      return;
    }
    if (open < n) {
      backtrack(cur + '(', open + 1, close);
    }
    if (close < open) {
      backtrack(cur + ')', open, close + 1);
    }
  }

  backtrack('', 0, 0);
  return result;
}

Reading it block by block

Line 2 — result array. All valid strings collect here. The outer function owns it; the inner recursive helper closes over it.

Lines 4–8 — base case. When the string reaches length 2 * n it is complete and valid (the two guards below prevent any invalid state from ever reaching this point). Push and return.

Lines 9–11 — add an open bracket. Allowed as long as open < n. We still have unused opens. Recurse with open + 1 and close unchanged.

Lines 12–14 — add a close bracket. Allowed only when close < open, meaning there is at least one unmatched open bracket. This single condition makes every produced string valid.

Line 18 — kick off. Start with an empty string, zero opens, zero closes. The two guards do all the work; no explicit backtracking or state restoration is needed because we pass immutable string values down the call stack.

Complexity → Time O(n · Cₙ) where Cₙ is the nth Catalan number — roughly 4ⁿ / n^3/2. Space O(n) for the call stack (depth ≤ 2n). The output is not counted in auxiliary space.

INTERVIEWFollow-ups they'll ask

"How many valid combinations exist for n?" The answer is the nth Catalan number C(n) = (2n choose n) / (n+1) — it grows exponentially, so you cannot do better than O(Cₙ) for output-sensitive enumeration.
"Can you do it iteratively?" Yes — use an explicit stack that stores (cur, open, close) tuples. The recursion stack becomes a data structure, logic stays the same.
"What if the brackets include [] and {} too?" Extend to three types of open brackets. Track a stack of currently open bracket types and only close the type on top of the stack (parentheses matching logic).
"Return the count, not the list?" That is exactly the Catalan number formula — compute it in O(n) with DP: C[i] = sum(C[j] * C[i-1-j]) for j in 0..i-1.
"Check a given string for validity?" That is LeetCode 20 — iterate characters, push opens onto a stack, pop on matching close, invalid if stack mismatches or non-empty at end.

OPTIMAL Backtracking

generateParenthesis.ts
function generateParenthesis(n: number): string[] {
  const result: string[] = [];

  function backtrack(cur: string, open: number, close: number): void {
    if (cur.length === 2 * n) {
      result.push(cur);
      return;
    }
    if (open < n) {
      backtrack(cur + '(', open + 1, close);
    }
    if (close < open) {
      backtrack(cur + ')', open, close + 1);
    }
  }

  backtrack('', 0, 0);
  return result;
}

Complexity → Time O(n · Cₙ) where Cₙ is the nth Catalan number — roughly 4ⁿ / n^3/2. Space O(n) for the call stack (depth ≤ 2n). The output is not counted in auxiliary space.

ALT 1 Brute force — generate all strings, keep the valid ones

O(2²ⁿ · n) time · O(2²ⁿ · n) space

Enumerate every length-2n string over ( and ), then keep only the balanced ones — validate at the end instead of pruning during construction.

approach-2.ts
function generateParenthesis(n: number): string[] {
  const result: string[] = [];

  // A string is valid if the running balance never goes negative
  // and ends at zero.
  function isValid(s: string): boolean {
    let bal = 0;
    for (const ch of s) {
      bal += ch === '(' ? 1 : -1;
      if (bal < 0) return false;
    }
    return bal === 0;
  }

  // Build all 2^(2n) sequences of '(' and ')'.
  function build(cur: string): void {
    if (cur.length === 2 * n) {
      if (isValid(cur)) result.push(cur);
      return;
    }
    build(cur + '(');
    build(cur + ')');
  }

  build('');
  return result;
}

Note → This explores all 2²ⁿ bracket strings even though only Cₙ ≈ 4ⁿ / n^(3/2)are valid — the vast majority are generated only to be thrown away. The two guards (open < n, close < open) prune invalid prefixes eagerly so only valid strings are ever built.

MNEMONIC The one-liner

"Open while open < n; close while close < open — never go invalid."

TRIGGERS When you see _ → reach for _

"all valid combinations" + bracket/structure type	backtracking + guards
enumerate strings with a local validity invariant	build-and-prune, not generate-and-filter
count of valid parenthesizations	Catalan number formula or DP
check if a single string is valid parens	stack: push open, pop on match

SKELETON The reusable shape

skeleton.ts
function generateParenthesis(n: number): string[] {
  const result: string[] = [];

  function backtrack(cur: string, open: number, close: number): void {
    if (cur.length === 2 * n) { result.push(cur); return; }
    if (open < n)    backtrack(cur + '(', open + 1, close);
    if (close < open) backtrack(cur + ')', open, close + 1);
  }

  backtrack('', 0, 0);
  return result;
}

FLASHCARDS Tap to flip

When can you add an open bracket?

When open < n — you still have unplaced opening brackets.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the pruned backtracking approach for generateParenthesis(n)?

QUESTION 02

Which condition guards adding an open bracket?

QUESTION 03

Trace n=2. Which of the following is NOT in the output?

QUESTION 04

Why does the algorithm never need to "undo" string modifications?

QUESTION 05

How many valid strings does generateParenthesis(3) return?

QUESTION 06

What is the maximum recursion depth for n=3?

QUESTION 07

An interviewer asks for the count of valid parenthesizations, not the list. Best approach?

QUESTION 08

#22 · Generate ParenthesesBacktracking with two counters: add "(" while open < n, add ")" while close < open. Record the string only when it reaches length 2n — yielding exactly the Catalan-number count of valid combinations.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Two pruning rules keep only valid states

RECIPE Backtrack with two guards

COST Complexity & alternatives

Space note

RUN IT Backtrack the decision tree: ( while open<n, ) while close<open

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Backtracking

ALT 1 Brute force — generate all strings, keep the valid ones

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _