Generate Parentheses — Backtracking with the Open and Close Counter Trick

Problem Statement#

LC 22 — Generate Parentheses. Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. A string is well-formed if every opening bracket has a matching closing bracket and brackets close in the correct order.

Constraints: 1 <= n <= 8. Output length is the n-th Catalan number C(n), so n = 8 produces 1430 strings.

Examples:

Input:  n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
 
Input:  n = 1  -> ["()"]
Input:  n = 2  -> ["(())","()()"]

Why This Problem Matters#

Generate Parentheses is the most common warm-up question on FAANG phone screens because it tests three skills in five minutes: a clean recursion structure, an invariant-based pruning rule, and the discipline to NOT generate invalid candidates and filter later. Amazon, Meta, Google, Microsoft, and Apple ask this almost weekly across teams.

The same open-and-close counter pattern appears in compiler design (matching brackets, expression parsing), JSON validators, regex parsers, and DOM tree builders. Once you master the counter invariant for parentheses, you have the recipe for any balanced-symbol enumeration problem (XML tags, multiple bracket types, prefix-balanced sequences).

This problem is also the gateway to Catalan numbers. The count of valid parenthesizations of n pairs is C(n) = (2n)! / ((n+1)! n!) and the same number counts binary trees with n nodes, monotonic lattice paths, and triangulations of a polygon. Interviewers love when candidates note the connection.

The Core Insight#

Two variables are sufficient to characterize any partial parenthesis string: the count of ( placed so far (open) and the count of ) placed so far (close). Any well-formed string of n pairs has exactly n opens and n closes, so the base case is open == n and close == n.

Two pruning rules prevent us from generating invalid prefixes in the first place:

• We can add ( only when open less-than n. Adding more than n opens is wasteful.
• We can add ) only when close less-than open. This is the load-bearing invariant: closes can never exceed opens at any prefix, which is exactly what makes the string well-formed.

Because every recursion either adds ( or ), the recursion depth is exactly 2n and each leaf is a complete valid string. No invalid string is ever generated, so there is zero post-filter cost — a hallmark of well-designed backtracking.

The decision tree branches at most twice per node (try (, then try )), so the total search tree has at most C(n) leaves. The state is just two integers and the current string, so memory is O(n) per recursion frame.

Visual Dry Run#

n = 2. Tree showing (open, close) and the string built so far.

bt("", 0, 0)
  add '(' -> bt("(", 1, 0)            # open less-than 2 OK
    add '(' -> bt("((", 2, 0)         # open == 2: cannot add more
      add ')' -> bt("(()", 2, 1)      # close less-than open OK
        add ')' -> bt("(())", 2, 2)   # base case -> RECORD
    add ')' -> bt("()", 1, 1)         # close less-than open OK
      add '(' -> bt("()(", 2, 1)      # open less-than 2 OK
        add ')' -> bt("()()", 2, 2)   # base case -> RECORD
      add ')' -> blocked              # close not less-than open

Final: ["(())", "()()"]. Two strings, exactly the second Catalan number.

Solution (Optimal)#

Python — counter-based backtracking template#

def generateParenthesis(n: int) -> list[str]:
    result: list[str] = []
 
    def bt(current: str, open_count: int, close_count: int) -> None:
        # Base case: used n opens and n closes -> well-formed string complete
        if len(current) == 2 * n:
            result.append(current)
            return
 
        # Try adding '(' if there is room for more opens
        if open_count < n:
            bt(current + '(', open_count + 1, close_count)
 
        # Try adding ')' only if it would not unbalance the prefix
        if close_count < open_count:
            bt(current + ')', open_count, close_count + 1)
 
    bt("", 0, 0)
    return result
 
 
# Variant: list-based path with explicit choose / unchoose, friendlier in some
# languages where string concatenation is expensive
def generateParenthesisList(n: int) -> list[str]:
    result: list[str] = []
    path: list[str] = []
 
    def bt(open_count: int, close_count: int) -> None:
        if len(path) == 2 * n:
            result.append(''.join(path))
            return
 
        if open_count < n:
            path.append('(')                 # choose
            bt(open_count + 1, close_count)  # explore
            path.pop()                       # unchoose
 
        if close_count < open_count:
            path.append(')')
            bt(open_count, close_count + 1)
            path.pop()
 
    bt(0, 0)
    return result

JavaScript#

function generateParenthesis(n) {
    const result = [];
 
    function bt(current, openCount, closeCount) {
        if (current.length === 2 * n) {
            result.push(current);
            return;
        }
        // Add '(' if open quota remains
        if (openCount < n) {
            bt(current + '(', openCount + 1, closeCount);
        }
        // Add ')' only when it preserves the well-formed prefix invariant
        if (closeCount < openCount) {
            bt(current + ')', openCount, closeCount + 1);
        }
    }
    bt("", 0, 0);
    return result;
}
 
// List-based variant using explicit choose / unchoose
function generateParenthesisList(n) {
    const result = [];
    const path = [];
 
    function bt(openCount, closeCount) {
        if (path.length === 2 * n) {
            result.push(path.join(''));
            return;
        }
        if (openCount < n) {
            path.push('(');
            bt(openCount + 1, closeCount);
            path.pop();
        }
        if (closeCount < openCount) {
            path.push(')');
            bt(openCount, closeCount + 1);
            path.pop();
        }
    }
    bt(0, 0);
    return result;
}

Complexity#

The bound 4^n / sqrt(n) is asymptotic to the n-th Catalan number times n (each output string has length 2n).

Common Mistakes#

1. Generating all 2^(2n) strings and filtering. This is exponentially worse than the counter approach. Always prune at construction time.
2. Using open less-than-or-equal n and close less-than-or-equal n as guards. These don't enforce well-formedness. The invariant is close less-than-or-equal open, not just that each is bounded by n.
3. Adding ) first, then (. Both branches are explored regardless of order, but the invariant guards depend on open already incrementing — beginners sometimes write if close less-than open before any open exists and get nothing in the result.
4. Forgetting the base case. Without len(current) == 2n you recurse forever. Always anchor the depth.
5. Mutating a shared list and recording without copy. When using the explicit list variant, ''.join(path) snapshots correctly; storing path directly stores a reference that becomes empty after backtracking.
6. Trying to memoize. Each leaf corresponds to a UNIQUE valid string — there is no shared subproblem to cache. Memoization is wasted memory here.

Interview Tips#

• Lead with the invariant. "I will track open and close counts. Two rules: don't exceed n opens, never let close exceed open." This is a 10-second sell.
• Mention Catalan numbers. Saying "the count is the n-th Catalan number" earns a smile; even a vague reference signals broader CS background.
• Choose string vs list deliberately. In Python, string concatenation is O(n) per operation; in JS, current + '(' allocates a new string each time. For small n this is fine; if asked to handle n = 20 you should switch to the list variant.
• Trace n = 2 aloud. Two outputs, four recursive calls — easy to verify by hand.
• Avoid the iterative DP solution unless asked. The DP angle exists (Catalan recurrence) but is harder to write under pressure.

Follow-up Questions#

• Generate parentheses with k types of brackets. Track an open stack instead of a counter and pop on close. State explodes — typically requires explicit stack.
• Count valid parenthesizations only (no enumeration). Catalan number formula: C(n) = (2n)! / ((n+1)! n!). O(n) DP, O(n) space.
• Validate a given string. Single counter pass: increment on (, decrement on ), fail if it goes negative or end value is not zero (LC 20 with two stack-style variants).
• Score parentheses (LC 856). Use a stack to evaluate scores; each balanced pair contributes a value.
• Different valid parentheses (LC 95 unique BSTs). Same Catalan recurrence applied to BST structure.

Key Takeaways#

• Track open and close counters to characterize every partial parenthesis string with two integers.
• Two pruning rules — open less-than n and close less-than open — make every generated candidate well-formed by construction, eliminating any post-filter step.
• Output count is the n-th Catalan number C(n), the same magical sequence that counts BSTs and lattice paths.
• Recursion depth is 2n and time complexity is O(4^n / sqrt(n)) — small enough that n = 8 runs in microseconds.
• This counter-driven invariant pattern transfers to balanced bracket languages of any kind: XML tags, multiple bracket types, and prefix-monotone sequences.
• Generate Parentheses is the warmest of warm-ups; nailing it signals fluency with backtracking templates and earns trust before harder follow-ups.