LeetCode · #22

Generate Parentheses Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #22

🏗️

Pattern

Backtracking — constrained generation

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses strings.

Example

 Input: n = 3 Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

Constraints

• 1 ≤ n ≤ 8

Section Two · Approach 1

Brute Force — Generate All & Filter

Generate all 2²ⁿ strings of length 2n using '(' and ')', then filter only valid ones. Validation uses a stack or counter — scan left-to-right, increment on '(', decrement on ')'. Valid if counter never goes negative and ends at 0.

Problem: Generates 2²ⁿ candidates, most invalid. Backtracking prunes invalid branches early — we never place a ')' unless there's an unmatched '(' to close. This reduces the search space to exactly the Catalan number Cₙ valid strings.

Metric	Value
Time	O(2²ⁿ · n) — generate + validate
Space	O(n) — recursion depth

Section Three · Approach 2

Backtracking — O(4ⁿ/√n)

Build the string character by character using two rules: (1) add '(' if we haven't used all n openers, (2) add ')' only if close < open (there's an unmatched opener to close). This guarantees every generated string is valid — no filtering needed.

💡 Mental model: Imagine building a staircase with n up-steps and n down-steps. You can always step up (add '(') if you haven't used all n ups. You can only step down (add ')') if you're above ground level — meaning you've gone up more times than down. You never go below ground. Every path from start to end at ground level is a valid parenthesization.

Algorithm

Base case: When open == n and close == n → add current string to result.
Choice 1: If open < n → recursively try adding '('.
Choice 2: If close < open → recursively try adding ')'.

🎯 Why close < open?:

If we've placed 3 openers and 2 closers so far, there's 1 unmatched '(' — so adding ')' is valid.
If close == open, there's nothing to close, so ')' would create an invalid prefix.
This single condition ensures validity without any post-filtering.

Section Four · Trace

Visual Walkthrough

Trace through n = 2:

Backtracking tree — n=2 (showing open/close counts)

Section Five · Implementation

Code — Java & Python

Java — Backtracking

 import java.util.*;
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
return result;
    }
private void backtrack(List<String> res, StringBuilder sb,
int open, int close, int n) {
if (sb.length() == 2 * n) {
            res.add(sb.toString());
return;
        }
if (open < n) {
            sb.append('(');
            backtrack(res, sb, open + 1, close, n);
            sb.deleteCharAt(sb.length() - 1); // undo
}
if (close < open) {
            sb.append(')');
            backtrack(res, sb, open, close + 1, n);
            sb.deleteCharAt(sb.length() - 1); // undo
}
    }
}

Python — Backtracking

 class Solution:
def generateParenthesis(self, n: int) -> list[str]:
        result = []
def backtrack(current: str, open: int, close: int):
if len(current) == 2 * n:
                result.append(current)
return if open < n:
                backtrack(current + "(", open + 1, close)
if close < open:
                backtrack(current + ")", open, close + 1)

        backtrack("", 0, 0)
return result

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Generate all + filter	O(2²ⁿ · n)	O(n)	Most candidates invalid
Backtracking ← optimal	O(4ⁿ/√n)	O(n)	Only valid strings generated. Count = Catalan number.

Catalan number:

The number of valid parenthesizations of n pairs is the n-th Catalan number Cₙ = (2n)! / ((n+1)! · n!).
For n=3: C₃=5, for n=8: C₈=1430. The bound O(4ⁿ/√n) comes from the asymptotic formula for Catalan numbers.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
n = 1	`1`	Only one string: "()".
n = 0	`0`	Edge — empty string [""] (not in constraints but worth knowing).
n = 8	`8`	Maximum input → 1430 valid strings. Runs fast.

⚠ Common Mistake: Forgetting to undo (backtrack) when using a mutable StringBuilder. After the recursive call returns, you must deleteCharAt to restore state. With Python's immutable strings (current + "("), this is automatic — a new string is created each time.

← Back to Stack problems

LearningTree

LC 22 · Generate Parentheses — Solution & Explanation | DSA Guide