22. Generate Parentheses (Medium)

Problem

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

Example

• n = 3 → ["((()))","(()())","(())()","()(())","()()()"]
• n = 1 → ["()"]

LeetCode 22 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, generate every 2n-char string, filter valid

Enumerate all 2^(2n) strings over {(, )}, keep the valid ones.

Python

def generate_parenthesis(n: int) -> list[str]:
    def is_valid(s):                               # helper: O(n) per call
        balance = 0
        for ch in s:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False
        return balance == 0

    result = []
    def rec(s):                                    # L1: recursive enumeration
        if len(s) == 2 * n:                        # L2: O(1) base-case check
            if is_valid(s):                        # L3: O(n) validation
                result.append(s)
            return
        rec(s + "(")                               # L4: recurse with open
        rec(s + ")")                               # L5: recurse with close
    rec("")
    return result

TypeScript

function generateParenthesis(n: number): string[] {
    function isValid(s: string): boolean {
        let balance = 0;
        for (const ch of s) {
            balance += ch === '(' ? 1 : -1;
            if (balance < 0) return false;
        }
        return balance === 0;
    }
    const result: string[] = [];
    function rec(s: string): void {                // L1: recursive enumeration
        if (s.length === 2 * n) {                  // L2: O(1) base-case check
            if (isValid(s)) result.push(s);        // L3: O(n) validation
            return;
        }
        rec(s + '(');                              // L4: recurse with open
        rec(s + ')');                              // L5: recurse with close
    }
    rec('');
    return result;
}

Go

func generateParenthesis(n int) []string {
    isValid := func(s string) bool {
        balance := 0
        for _, ch := range s {
            if ch == '(' { balance++ } else { balance-- }
            if balance < 0 { return false }
        }
        return balance == 0
    }
    result := []string{}
    var rec func(s string)
    rec = func(s string) {                         // L1: recursive enumeration
        if len(s) == 2*n {                         // L2: O(1) base-case check
            if isValid(s) { result = append(result, s) } // L3: O(n) validation
            return
        }
        rec(s + "(")                               // L4: recurse with open
        rec(s + ")")                               // L5: recurse with close
    }
    rec("")
    return result
}

Swift

final class Solution {
    func generateParenthesis(_ n: Int) -> [String] {
        var result: [String] = []
        var path: [Character] = []
        func generate(_ index: Int) {
            if index == 2 * n {
                var balance = 0
                for character in path {
                    balance += character == "(" ? 1 : -1
                    if balance < 0 { return }
                }
                if balance == 0 { result.append(String(path)) }
                return
            }
            path.append("(")
            generate(index + 1)
            path[path.count - 1] = ")"
            generate(index + 1)
            path.removeLast()
        }
        generate(0)
        return result
    }
}

Where the time goes, line by line

Variables: n = number of pairs, C(n) = n-th Catalan number.

Line	Per-call cost	Times executed	Contribution
L1-L5 (full enumeration)	$O(n)$ at leaves	4^n nodes	$O(4^n · n)$ ← dominates
L3 (is_valid at leaf)	$O(n)$	4^n leaves	$O(4^n · n)$

The recursion tree has 4^n leaves (all 2n-length strings of ( and )); each is validated in $O(n)$.

Complexity

• Time: $O(2^{2n} \cdot n)$, driven by L1-L5 (exponentially many strings, each validated in $O(n)$).
• Space: $O(n)$ recursion depth (plus output).

Approach 2: Prune invalid strings during generation

Track running balance during the recursion. Abort a branch as soon as close > open or open > n.

Python

def generate_parenthesis(n: int) -> list[str]:
    result = []
    def rec(s, opens, closes):                     # L1: pruned recursion
        if opens > n or closes > opens:            # L2: O(1) prune check
            return
        if len(s) == 2 * n:                        # L3: O(1) base case
            result.append(s)
            return
        rec(s + "(", opens + 1, closes)            # L4: try open
        rec(s + ")", opens, closes + 1)            # L5: try close
    rec("", 0, 0)
    return result

TypeScript

function generateParenthesis(n: number): string[] {
    const result: string[] = [];
    function rec(s: string, opens: number, closes: number): void {  // L1: pruned recursion
        if (opens > n || closes > opens) return;                     // L2: O(1) prune check
        if (s.length === 2 * n) { result.push(s); return; }         // L3: O(1) base case
        rec(s + '(', opens + 1, closes);                             // L4: try open
        rec(s + ')', opens, closes + 1);                             // L5: try close
    }
    rec('', 0, 0);
    return result;
}

Go

func generateParenthesis(n int) []string {
    result := []string{}
    var rec func(s string, opens, closes int)
    rec = func(s string, opens, closes int) {      // L1: pruned recursion
        if opens > n || closes > opens { return }  // L2: O(1) prune check
        if len(s) == 2*n { result = append(result, s); return } // L3: O(1) base case
        rec(s+"(", opens+1, closes)                // L4: try open
        rec(s+")", opens, closes+1)                // L5: try close
    }
    rec("", 0, 0)
    return result
}

Swift

final class Solution {
    func generateParenthesis(_ n: Int) -> [String] {
        var result: [String] = []
        func generate(_ current: String, _ opens: Int, _ closes: Int) {
            if current.count == 2 * n { result.append(current); return }
            if opens < n { generate(current + "(", opens + 1, closes) }
            if closes < opens { generate(current + ")", opens, closes + 1) }
        }
        generate("", 0, 0)
        return result
    }
}

Where the time goes, line by line

Variables: n = number of pairs, C(n) = n-th Catalan number.

Line	Per-call cost	Times executed	Contribution
L2 (prune check)	$O(1)$	at each node	reduces tree to ~4·C(n) nodes
L4, L5 (recurse)	$O(n)$ at leaves	C(n) leaves	$O(C(n)$ · n) ← dominates

Pruning reduces the explored space from 4^n to the Catalan number C(n) ≈ 4^n / (n^(3/2) · sqrt(pi)).

Complexity

• Time: $O(4^n / sqrt(n)$), the n-th Catalan number times a linear factor. Much smaller than the brute-force 4^n.
• Space: $O(n)$ recursion depth.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Backtracking with the exact open/close invariant (optimal)

Same idea, phrased so the invariants are explicit: at each step you can add ( if opens < n, and ) if closes < opens.

Python

def generate_parenthesis(n: int) -> list[str]:
    result = []                                    # L1: O(1)
    path = []                                      # L2: O(1) shared path buffer

    def backtrack(opens, closes):
        if opens == n and closes == n:             # L3: O(1) done check
            result.append("".join(path))           # L4: O(n) join at leaf
            return
        if opens < n:                              # L5: O(1)
            path.append("(")                       # L6: O(1) amortized
            backtrack(opens + 1, closes)           # L7: recurse
            path.pop()                             # L8: O(1) undo
        if closes < opens:                         # L9: O(1)
            path.append(")")                       # L10: O(1) amortized
            backtrack(opens, closes + 1)           # L11: recurse
            path.pop()                             # L12: O(1) undo

    backtrack(0, 0)
    return result

TypeScript

function generateParenthesis(n: number): string[] {
    const result: string[] = [];                   // L1: O(1)
    const path: string[] = [];                     // L2: O(1) shared path buffer

    function backtrack(opens: number, closes: number): void {
        if (opens === n && closes === n) {         // L3: O(1) done check
            result.push(path.join(''));            // L4: O(n) join at leaf
            return;
        }
        if (opens < n) {                          // L5: O(1)
            path.push('(');                       // L6: O(1) amortized
            backtrack(opens + 1, closes);         // L7: recurse
            path.pop();                           // L8: O(1) undo
        }
        if (closes < opens) {                     // L9: O(1)
            path.push(')');                       // L10: O(1) amortized
            backtrack(opens, closes + 1);         // L11: recurse
            path.pop();                           // L12: O(1) undo
        }
    }

    backtrack(0, 0);
    return result;
}

Go

func generateParenthesis(n int) []string {
    result := []string{}                           // L1: O(1)
    path := []string{}                             // L2: O(1) shared path buffer
    var backtrack func(opens, closes int)
    backtrack = func(opens, closes int) {
        if opens == n && closes == n {             // L3: O(1) done check
            result = append(result, strings.Join(path, "")) // L4: O(n) join at leaf
            return
        }
        if opens < n {                             // L5: O(1)
            path = append(path, "(")              // L6: O(1) amortized
            backtrack(opens+1, closes)             // L7: recurse
            path = path[:len(path)-1]             // L8: O(1) undo
        }
        if closes < opens {                        // L9: O(1)
            path = append(path, ")")              // L10: O(1) amortized
            backtrack(opens, closes+1)             // L11: recurse
            path = path[:len(path)-1]             // L12: O(1) undo
        }
    }
    backtrack(0, 0)
    return result
}

Swift

final class Solution {
    func generateParenthesis(_ n: Int) -> [String] {
        var result: [String] = []
        var path: [Character] = []
        func backtrack(_ opens: Int, _ closes: Int) {
            if opens == n && closes == n { result.append(String(path)); return }
            if opens < n {
                path.append("(")
                backtrack(opens + 1, closes)
                path.removeLast()
            }
            if closes < opens {
                path.append(")")
                backtrack(opens, closes + 1)
                path.removeLast()
            }
        }
        backtrack(0, 0)
        return result
    }
}

Where the time goes, line by line

Variables: n = number of pairs, C(n) = n-th Catalan number.

Line	Per-call cost	Times executed	Contribution
L3-L4 (base case + join)	$O(n)$	C(n) leaves	$O(C(n)$ · n)
L5-L12 (append/recurse/pop)	$O(1)$ amortized	~4·C(n) nodes	$O(C(n)$)
Total			$O(C(n)$ · n) ← dominates

Using a single path list with append/pop avoids $O(n)$ string concatenation on each internal node; the join cost $O(n)$ is paid only at the C(n) leaves.

Complexity

• Time: $O(4^n / sqrt(n)$), driven by L4/L7/L11 (Catalan-many recursive calls). Same asymptotic as Approach 2; the count of well-formed sequences is the n-th Catalan number.
• Space: $O(n)$ recursion depth + output.

Using a single path list with append/pop avoids string concatenation ($O(n)$ per append); the final join happens only on full paths.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Enumerate all + validate	$O(2^{2n} \cdot n)$	$O(n)$
Prune during generation	$O(4^n / sqrt(n)$)	$O(n)$
Backtracking with invariants	$O(4^n / sqrt(n)$)	$O(n)$

Approach 3 is the canonical answer and the cleanest expression of the idea. The output is inherently exponential, so you can’t beat the Catalan bound.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_generate_parentheses.py and run.
# Uses the canonical implementation (Approach 3: backtracking with invariants).

def generate_parenthesis(n: int) -> list[str]:
    result = []
    path = []

    def backtrack(opens, closes):
        if opens == n and closes == n:
            result.append("".join(path))
            return
        if opens < n:
            path.append("(")
            backtrack(opens + 1, closes)
            path.pop()
        if closes < opens:
            path.append(")")
            backtrack(opens, closes + 1)
            path.pop()

    backtrack(0, 0)
    return result

def _run_tests():
    assert sorted(generate_parenthesis(1)) == ["()"]
    assert sorted(generate_parenthesis(2)) == sorted(["(())", "()()"])
    assert sorted(generate_parenthesis(3)) == sorted(["((()))","(()())","(())()","()(())","()()()"])
    assert len(generate_parenthesis(4)) == 14   # 4th Catalan number
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function generateParenthesis(n: number): string[] {
    const result: string[] = [];
    const path: string[] = [];
    function backtrack(opens: number, closes: number): void {
        if (opens === n && closes === n) { result.push(path.join('')); return; }
        if (opens < n) { path.push('('); backtrack(opens + 1, closes); path.pop(); }
        if (closes < opens) { path.push(')'); backtrack(opens, closes + 1); path.pop(); }
    }
    backtrack(0, 0);
    return result;
}

console.assert(JSON.stringify(generateParenthesis(1).sort()) === JSON.stringify(['()']));
console.assert(JSON.stringify(generateParenthesis(2).sort()) === JSON.stringify(['(())', '()()'].sort()));
console.assert(generateParenthesis(4).length === 14);
console.log('all tests pass');

Related data structures

• Stacks, the recursion stack is the backtracking frontier

Related concepts

• Backtracking, the explore, undo, and prune pattern for building candidates.
• Stack Parsing, the last open, first closed model for nested syntax and reversible operations.