Generate Parentheses: Backtracking With Two Counts

Valid Parentheses asks whether one string is well formed. Generate Parentheses, LeetCode 22, rated Medium, asks you to emit every well-formed string that uses exactly n pairs. Amazon, Meta, and Google all use some version of it, not because the code is long, but because it is the cleanest backtracking question they can ask in twenty minutes.

The brute force is obvious and wrong for the clock: generate every string of length 2n over ( and ), then filter with a stack. There are 2^{2n} candidates. The interview is whether you prune while you build, so every leaf you reach is already valid.

The Problem

Given n, return all strings made of n pairs of correctly matched parentheses. Order of the output does not matter.

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

For n = 1 the only answer is "()". For n = 2 there are two: "(())" and "()()". "())(" is never in the list, and neither is "(()".

Recognizing the Backtracking Pattern

Backtracking is depth-first search on an implicit tree of partial answers. At each node you try a choice, recurse, then undo the choice so the sibling can use the same buffer. Combinatorial generation — subsets, permutations, combination sum, letter combinations of a phone number — is this skeleton with a different choice set.

The art is the prune. You never walk a branch that cannot become valid, so you do not spend time validating at the leaves. Two inequalities are the entire rule set:

• You may append ( if you have used fewer than n openers.
• You may append ) if you have used fewer closers than openers so far.

That second rule is the stack invariant from Valid Parentheses, encoded as two integers. A closer that would make closed > opened is a prefix that no suffix can repair. Cutting that branch is the whole trick.

The number of valid strings is the Catalan number C_n = (1 / (n + 1)) * C(2n, n). The first few values are worth having in your head: C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42. If your function returns 6 strings for n = 3, you generated an invalid one.

The Approach

Keep a shared path buffer and two counters, opened and closed. Recurse. When the buffer length is 2n, snapshot a string into the result. After each recursive call, pop so the buffer again equals the prefix for the current node.

Do not call isValid at the leaf. If you only ever placed a closer when closed < opened, every complete string is valid by construction. Saying that sentence is how you show you own the invariant rather than cargo-culting a template.

Two equivalent implementations exist. Mutating a list and popping is the backtracking you can point at on the whiteboard. Passing s + "(" creates a new string per call, so there is nothing to undo. Both are O(n) extra work per edge of the search tree. Prefer the list if they asked you to demonstrate backtracking; prefer the immutable string if you want fewer moving parts.

Python Solution

def generate_parenthesis(n: int) -> list[str]:
    """All well-formed strings of n parenthesis pairs."""
    result: list[str] = []
    path: list[str] = []

    def dfs(opened: int, closed: int) -> None:
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        if opened < n:
            path.append("(")
            dfs(opened + 1, closed)
            path.pop()
        if closed < opened:
            path.append(")")
            dfs(opened, closed + 1)
            path.pop()

    dfs(0, 0)
    return result

The pop after each recursive call is the same restore used in Path Sum II. Forget it and every path aliases one mutating buffer; the result list fills with copies of the last string, or with empty strings if you also clear the buffer at the end.

Walkthrough for n = 2

Start at (opened=0, closed=0). A closer is illegal, so the first character is always (.

• "(" → can open or close.
  • "((" → can only close (opened == n). Then "(())" and we are done.
  • "()" → opened == closed == 1, so a second closer is illegal. Open: "()(", then close: "()()".

The invalid prefixes "())" and ")" never appear as nodes. That is the prune doing its job. Draw this tree if they hand you a marker: five nodes of depth at most 4, not the sixteen bitstrings of length 4.

Complexity

• Time: O(C_n · n) — there are C_n leaves, and joining a path of length 2n at each leaf is O(n). The internal nodes of the pruned tree are a constant factor on the same order, not the full 2^{2n} binary tree.
• Space: O(n) for the path and the call stack, plus O(C_n · n) for the output, which you do not count against the algorithm unless they ask you to.

LeetCode constraints put n in [1, 8]. C_8 is 1430, so the output is small. The reason to quote Catalan anyway is to show you know the search tree is not exponential in the naive sense.

The generate-and-filter answer they are waiting to reject

# Do not ship this. It is the answer that proves you have not named the prune.
from itertools import product

def generate_parenthesis_slow(n: int) -> list[str]:
    out = []
    for bits in product("()", repeat=2 * n):
        s = "".join(bits)
        if is_valid(s):          # the stack from Valid Parentheses
            out.append(s)
    return out

For n = 8 that is 65,536 candidates, most of them invalid. The backtracking version never builds them. If they ask "why not generate all," say the prefix invariant, not "it is slower." Slow is a symptom. Exploring illegal prefixes is the cause.

Interview Tips and Follow-Ups

• n = 0. Ask. An empty list and a list containing "" are both defensible; the usual constraint starts at 1, so they are probing whether you clarify.
• Order. Do not sort unless they require a specific order. Opening-first DFS emits a stable order as a side effect; do not promise it.
• Count only, do not list. That is Catalan, or the DP dp[i] = sum(dp[j] * dp[i - 1 - j] for j in range(i)) with dp[0] = 1. The term dp[j] * dp[i - 1 - j] is the decomposition (A)B: a valid string of j pairs inside one wrapping pair, then a valid string of i - 1 - j pairs. If they want the count in O(n) arithmetic after computing a binomial, say so; if they want you to show the recurrence, write the DP.
• Three bracket types. The two counters are not enough. The state needs a stack of unmatched openers (or an equivalent encoding of the top), because ([)] keeps both counts legal and is still invalid. This is the same reason a single depth counter fails Valid Parentheses.
• Immutable variant. dfs(s + "(", opened + 1, closed) is acceptable. Mention that Python strings are immutable, so you did not actually mutate-and-undo; you branched. Interviewers who just taught backtracking on arrays may want to see the pop.

Generate Parentheses is Valid Parentheses run backwards: the stack invariant becomes two integers, and the output is every string that would have left the stack empty. The same append-recurse-pop skeleton is behind Subsets, Permutations, and Combination Sum. More of that family sits in the Technical Interview category.