Generate Parentheses (LC 22)

Pattern: Backtracking
Difficulty: Medium
Key Concept: Only extend strings that can still become valid: add '(' while open < n, add ')' while close < open.

Problem Statement

Given n pairs of parentheses, return all strings of well-formed (balanced) parentheses using exactly n opening and n closing brackets.

Input

• n: non-negative integer — number of pairs (so string length 2n).

Output

• List<String> — every distinct valid parentheses string of length 2n.

Example

• n = 3
• One valid string: "((()))"; full answer has 5 strings (Catalan number C_3).

---

1. Algorithm & Pseudocode

Brute force

result = empty
for each of 2^(2n) strings over '(' and ')':
    if isValid(string): result.add(string)
return result
isValid: scan, balance never negative and ends at 0 — O(n) per string

Optimal — backtracking with counters

result = empty
sb = empty StringBuilder

backtrack(open, close):
    if open == n && close == n:
        result.add(sb.toString())
        return
    if open < n:
        sb.append('(')
        backtrack(open + 1, close)
        sb.deleteCharAt(sb.length() - 1)
    if close < open:
        sb.append(')')
        backtrack(open, close + 1)
        sb.deleteCharAt(sb.length() - 1)

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why not generate all 2^(2n) strings? Most strings are invalid. Checking each costs O(n) → O(n · 2^(2n)) total, far worse than only building valid prefixes.

2. State open and close — open = count of '(' placed so far; close = count of ')'. Valid partial strings always satisfy close <= open (never more closing than opening at any prefix).

3. **When can we add '('?** While open < n` — we have not used all opening slots.

4. When can we add ')'? While close < open — each ')' must close an existing unmatched '('.

5. Why StringBuilder in Java? String concatenation creates new String objects each time (immutable). StringBuilder mutates a buffer; append and delete last support backtracking with less allocation.

---

3. The Dry Run

Sample: n = 3. Track sb, open, close. Leaf when open == 3 && close == 3.

Step	Action	sb (content)	open	close
1	append (	(	1	0
2	append (	((	2	0
3	append (	(((	3	0
4	append )	((()	3	1
5	append )	((())	3	2
6	append )	((()))	3	3
…	(tree continues)	—	—	—

Decision tree (root = empty, edges = append ( then explore, or ) when allowed)

                         ""
                    /         \
                  "("          (only if open<n — ")" illegal here)
                 /   \
            "(("     "()" ...
            /  \
        "((("  "(()"
         ...

All five leaves for n = 3:
((())), (()()), (())(), ()(()), ()()().

Trace table — first complete path and sibling sketch

Step	sb	open	close	Next choice
A	``	0	0	must add (
B	(	1	0	( or ) illegal
C	((	2	0	(
D	(((	3	0	( blocked; add )
E	((()	3	1	add )
F	((())	3	2	add )
G	((()))	3	3	record, backtrack

---

4. Java Solution

Brute Force

Generate all 2^(2n) strings, validate each.

Time: O(n · 2^(2n))
Space: O(n) for recursion/stack of validation + builder

import java.util.*;

class SolutionBrute {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] buf = new char[2 * n];
        brute(0, buf, result);
        return result;
    }

    private void brute(int pos, char[] buf, List<String> result) {
        if (pos == buf.length) {
            if (isValid(buf)) result.add(new String(buf));
            return;
        }
        buf[pos] = '(';
        brute(pos + 1, buf, result);
        buf[pos] = ')';
        brute(pos + 1, buf, result);
    }

    private boolean isValid(char[] s) {
        int bal = 0;
        for (char c : s) {
            if (c == '(') bal++;
            else bal--;
            if (bal < 0) return false;
        }
        return bal == 0;
    }
}

Optimal

import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(new StringBuilder(), 0, 0, n, result);
        return result;
    }

    private void backtrack(StringBuilder sb, int open, int close, int n, List<String> result) {
        if (open == n && close == n) {
            result.add(sb.toString());
            return;
        }
        if (open < n) {
            sb.append('(');
            backtrack(sb, open + 1, close, n, result);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (close < open) {
            sb.append(')');
            backtrack(sb, open, close + 1, n, result);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

---

5. The “Java vs. Others” Edge

• StringBuilder.append / deleteCharAt(length-1) — Mutable buffer; O(1) amortized append; delete last char is O(1) at the end. String s + "(" allocates a new String every time — poor for deep recursion.
• C++ — string::push_back / pop_back is the usual pattern.
• Python — strings are immutable; people often use list of chars and join, or keep concatenating (slower) in naive code.
• Java String immutability — Makes StringBuilder the standard tool for incremental construction in backtracking.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n · 2^(2n))	O(n) auxiliary + output	2^(2n) candidates, O(n) validate each
Optimal	O(4^n / √n) catalytic scale; O(n) per answer × Catalan answers	O(n) stack + StringBuilder	Only valid prefixes; Catalan C_n ≈ 4^n/(n^(3/2)√π)

Number of valid strings = nth Catalan number C_n.