LeetCode 22 – Generate Parentheses

Generate Parentheses is the problem that teaches constrained backtracking. The lazy solution generates all 2²ⁿ strings of brackets and filters out the invalid ones. The intended solution never builds an invalid string in the first place, because two small rules make it impossible — and understanding why those two rules are sufficient is the whole exercise.

The problem

Given n pairs of parentheses, generate every well-formed combination.

n = 3 -> ["((()))", "(()())", "(())()", "()(())", "()()()"]
n = 1 -> ["()"]

The two rules

At every step you are choosing the next character, and there are only two candidates. Each has exactly one condition:

You may add ( while fewer than n have been used. There are only n pairs, so that is simply the supply running out.
You may add ) only while close < open. A closing bracket has to close something. If as many have been closed as opened, there is nothing open to close, and adding one makes the string invalid forever — no later character can repair it.

That second rule is the one doing the real work, and it is worth stating precisely: a string of brackets is well-formed exactly when no prefix has more ) than (, and the totals match at the end. The rule enforces the prefix condition at every single step, and running until the string reaches length 2n enforces the totals. So every leaf of the recursion is valid by construction. There is nothing to filter.

Notice what is not needed: no stack, no validity check, no scan of the string built so far. Two integer counters carry all the state that matters.

Backtracking: append, recurse, undo

Build into one shared StringBuilder rather than passing a fresh String down each branch. Java strings are immutable, so dfs(sb + "(") copies the entire prefix at every node of the recursion tree — it works, and it adds a factor of n to the cost for nothing.

The price of sharing the buffer is that you must undo your move after the recursive call returns, so the next branch starts from the state it expects. Append, recurse, delete the last character. Forgetting that final delete is the classic backtracking bug, and it produces output that looks almost right, which makes it slow to spot.

Java

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> result, StringBuilder sb,
                           int open, int close, int n) {
        if (sb.length() == 2 * n) {     // used all n pairs
            result.add(sb.toString());
            return;
        }

        if (open < n) {                 // supply of '(' not exhausted
            sb.append('(');
            backtrack(result, sb, open + 1, close, n);
            sb.deleteCharAt(sb.length() - 1);   // undo
        }

        if (close < open) {             // only close what is actually open
            sb.append(')');
            backtrack(result, sb, open, close + 1, n);
            sb.deleteCharAt(sb.length() - 1);   // undo
        }
    }
}

sb.toString() at the leaf makes a copy, which is necessary — the buffer keeps mutating after the result is recorded. Adding sb itself would leave every entry in the list pointing at the same object, and you would finish with n copies of an empty string.

Python

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        result = []
        path = []

        def backtrack(open_count: int, close_count: int) -> None:
            if len(path) == 2 * n:
                result.append("".join(path))     # copy: path keeps mutating
                return

            if open_count < n:
                path.append("(")
                backtrack(open_count + 1, close_count)
                path.pop()                       # undo

            if close_count < open_count:
                path.append(")")
                backtrack(open_count, close_count + 1)
                path.pop()                       # undo

        backtrack(0, 0)
        return result

A list of characters plus "".join is the Python equivalent of StringBuilder. Building with path + "(" on an immutable string has the same copying cost as in Java.

Complexity

The number of well-formed strings for n pairs is the nth Catalan number, C(2n, n) / (n + 1), which grows like 4ⁿ / n^1.5. Each result takes O(n) to copy out, so the total is O(4ⁿ / √n) time. Space is O(n) for the buffer and the recursion depth, not counting the output.

Compare that with generate-and-filter: 2²ⁿ = 4ⁿ candidates, each needing an O(n) validity check. The pruned version is asymptotically better by a factor of √n — but the real difference is bigger than that comparison suggests, because the pruning cuts entire subtrees the moment they become hopeless, rather than after building them out in full.

You are not expected to derive the Catalan number in an interview. Saying "the output itself is exponential, so no algorithm can be polynomial — this one does O(1) work per node of a tree whose leaves are exactly the answers" is the answer that counts.

What the interviewer is checking

That you prune instead of generating everything and filtering.
That you can justify close < open — not just state it.
That you undo the move after recursing.
That you copy the buffer into the result rather than storing a reference to it.
That you build into a mutable buffer, not by concatenating immutable strings.
That you recognise the output size is exponential and that this bounds any possible solution.