Generate Parentheses

1. Problem & Core Objective

The problem

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

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

Input:  n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

What the interviewer is actually testing

Despite sitting in the Stack section, this is a backtracking problem — the stack is the recursion itself, never an explicit data structure.

1. Do you generate only valid strings, rather than generating everything and filtering? The difference between 4^n and Catalan-many is enormous, and the filtering version is the obvious-but-wrong first instinct.
2. Can you state the two rules that make invalidity impossible? open < n and close < open. That second one is the entire correctness argument.
3. Do you notice n <= 8? A tiny bound is the interviewer telling you exponential output is expected — stop looking for a polynomial algorithm.
4. Do you handle the un-choose step? Appending to a shared StringBuilder requires removing the character after recursing.

2. First-Principles Thought Process

Step 1 — Read the constraint as a signal

1 <= n <= 8. That's a very small bound, and it isn't an accident.

The number of valid strings for n pairs is the Catalan number C(n):

So even at n = 8 there are only 1430 answers. The output itself is exponential, so no algorithm can be polynomial — you must produce every result, and that's the floor. The goal is therefore not to avoid exponential work but to avoid exploring branches that produce nothing.

Small constraint + "return all" ⇒ backtracking. See 15 — Backtracking.

Step 2 — The obvious approach, and why it wastes

Generate every string of length 2n over {'(' , ')'} — there are 2^(2n) = 4^n of them — then filter for validity.

At n = 8: 4^8 = 65,536 candidates, of which only 1430 are valid. 98% of the work is discarded. And at larger n the ratio gets far worse.

Step 3 — The reframe: make invalid states unreachable

Rather than generating freely and checking afterwards, only ever make a choice that cannot lead to invalidity.

At any point during construction, you've placed open opening brackets and close closing ones. Two rules:

Rule 1 — you may add ( only if open < n. You have n pairs total, so you can't open more than n.

Rule 2 — you may add ) only if close < open. A closing bracket must match an already-open one. If close == open, everything opened has been closed, and another ) would have nothing to match.

Step 4 — Why those two rules are sufficient

This is the correctness argument, and it's what the question is really testing:

A string is valid iff, reading left to right, the count of ) never exceeds the count of (, and the totals are equal at the end.

Rule 2 enforces the first condition at every step — close can never exceed open. Rule 1 caps open at n, and the recursion stops at length 2n, which forces close == open == n at every leaf.

So every leaf of the recursion is a valid string, and no validity check is ever needed.

That's a stronger claim than "we filter as we go" — the invalid branches are never entered at all.

Step 5 — Where the stack is

There's no explicit stack in the solution. But the recursion's call stack is the bracket stack: each pending ( corresponds to a frame waiting to close. That's why this problem sits in the Stack section — the same LIFO structure as Valid Parentheses, made implicit.

3. Solution Paths

Approach 1 — Generate all, then filter

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    generate(new char[2 * n], 0, res);
    return res;
}

private void generate(char[] cur, int i, List<String> res) {
    if (i == cur.length) {
        if (isValid(cur)) res.add(new String(cur));
        return;
    }
    cur[i] = '(';  generate(cur, i + 1, res);
    cur[i] = ')';  generate(cur, i + 1, res);
}

private boolean isValid(char[] cur) {
    int balance = 0;
    for (char c : cur) {
        balance += (c == '(') ? 1 : -1;
        if (balance < 0) return false;
    }
    return balance == 0;
}

• Time: O(2^(2n) · n) — 4^n candidates, each validated in O(n).
• Space: O(n) recursion depth, plus the output.

Counter-questions on this approach

⭐ "How much of this work is wasted?"

At n = 8, it generates 65,536 strings and keeps 1430 — about 98% discarded. And the ratio worsens as n grows, since 4^n outpaces the Catalan numbers. The fix isn't to filter faster; it's to never generate the invalid branches at all.

"Could you at least prune early — abandon a prefix once it's already invalid?"

Yes, and that's precisely the insight that leads to the optimal solution. If I check validity during construction rather than at the leaves, I stop descending the moment close > open. Formalizing "never let that happen" gives the two rules, and then the check disappears entirely because the state is unreachable.

Approach 2 — Backtracking with the two rules (optimal)

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

private void backtrack(int open, int close, int n, StringBuilder sb, List<String> res) {
    if (sb.length() == 2 * n) {
        res.add(sb.toString());
        return;
    }

    if (open < n) {                       // Rule 1: can still open a new pair
        sb.append('(');
        backtrack(open + 1, close, n, sb, res);
        sb.setLength(sb.length() - 1);    // UN-CHOOSE
    }
    if (close < open) {                   // Rule 2: can only close what is open
        sb.append(')');
        backtrack(open, close + 1, n, sb, res);
        sb.setLength(sb.length() - 1);    // UN-CHOOSE
    }
}

Full decision tree for n = 2:

                    ""  (0,0)
                     |
                    "("  (1,0)          ← only '(' is legal; close < open fails
                   /     \
        "(("  (2,0)       "()"  (1,1)
              |                  |
        "(()"  (2,1)       "()("  (2,1)   ← open<n fails for "((", close<open fails for "()"
              |                  |
       "(())" ✓            "()()" ✓

Two leaves, both valid — matching C(2) = 2. No invalid string is ever constructed.

• Time: O(4^n / √n) — the Catalan number times O(n) to build each string. Every node explored leads to at least one answer.
• Space: O(n) recursion depth and the StringBuilder, excluding the output.

Counter-questions on this approach

⭐ "Prove that every string you produce is valid — you never run a validity check."

A string of brackets is valid iff, scanning left to right, the running count of ) never exceeds (, and the totals match at the end.

Rule 2 (close < open) guarantees the first condition at every step — I can never place a ) that would make closers exceed openers. Rule 1 caps open at n, and I stop at length 2n, which forces open == close == n at every leaf. So both conditions hold by construction, and the check is unnecessary rather than omitted.

⭐ "What's the actual complexity? O(2^n) isn't right."

The number of results is the n-th Catalan number, asymptotically 4^n / (n^(3/2)√π). Each result costs O(n) to materialize, giving O(4^n / √n) overall. That's the honest bound.

More usefully: the output alone is Catalan-many, so exponential is a floor, not a failing. What matters is that this explores only nodes that lead to real answers — unlike the filter version, which explores 4^n.

"Why sb.setLength(sb.length() - 1) rather than building a new string at each call?"

Passing an immutable String and concatenating would allocate a new O(n) string at every node — and there are exponentially many nodes. A shared StringBuilder with an explicit un-choose reuses one buffer. The setLength call is the backtracking step: it restores the state so the sibling branch starts clean.

"What happens if you forget the setLength?"

The StringBuilder keeps growing and the second branch sees a polluted prefix — you'd get wrong strings and the length check would fire at the wrong times. Every append before a recursive call needs a matching removal after it. Counting appends against removals is the discipline that prevents this class of bug.

"Is passing an immutable String instead ever acceptable?"

It works and is arguably cleaner — backtrack(open+1, close, n, s + "(", res) needs no un-choose at all, since each call has its own string. The cost is O(n) allocation per node. At n <= 8 that's completely fine, so I'd accept it; at larger bounds the StringBuilder matters.

Approach 3 — Closure-number recursion

public List<String> generateParenthesis(int n) {
    if (n == 0) return List.of("");

    List<String> res = new ArrayList<>();
    for (int i = 0; i < n; i++) {                      // i pairs INSIDE the first bracket
        for (String inner : generateParenthesis(i)) {
            for (String rest : generateParenthesis(n - 1 - i)) {   // the remainder AFTER it
                res.add("(" + inner + ")" + rest);
            }
        }
    }
    return res;
}

How it works. Every valid string has a unique decomposition: the first ( closes at some position, splitting the string into "(" + inner + ")" + rest, where inner has i pairs and rest has n − 1 − i. Enumerating i from 0 to n−1 covers every string exactly once.

This is the direct combinatorial construction — and the recurrence it encodes, C(n) = Σ C(i)·C(n−1−i), is the definition of the Catalan numbers.

• Time: same asymptotic output-bound, but slower in practice from repeated sub-calls and string concatenation.
• Space: O(n) depth plus intermediate lists.

Counter-questions on this approach

⭐ "This recomputes generateParenthesis(i) many times. Would memoizing help?"

Yes — caching results by n turns the repeated sub-calls into lookups, and it's a genuine improvement. But the dominant cost is still materializing exponentially many strings, so it's a constant-factor win. The backtracking version avoids the issue entirely by building each string once, in place.

"Why is this worth knowing if it's slower?"

Because it makes the structure explicit. The C(n) = Σ C(i)·C(n−1−i) recurrence it encodes is the Catalan definition, which is also why the answer count is what it is. If the interviewer asks "how many results are there?", this decomposition is the derivation.

Comparison

4. Why the Optimal Wins

Against generate-and-filter. Both produce the same answers, but the filter version explores 4^n nodes to find Catalan-many results. The backtracking version explores only nodes that lead to at least one valid string. At n = 8 that's 65,536 candidates versus 1430 — a factor of 45, growing with n.

The principle, which transfers well beyond this problem:

Don't generate then validate. Make invalid states unreachable by construction.

The same move appears in N-Queens (never place a queen on an attacked square rather than checking afterwards) and in constraint propagation generally.

Against the closure recursion. Same asymptotic bound, but it re-solves subproblems and builds strings by concatenation rather than in place. Its value is explanatory — it derives the Catalan count.

How to talk about exponential complexity here — don't apologize for it:

"The output alone has Catalan-many strings, roughly 4^n / √n, so no algorithm can be polynomial — producing the answer takes that long. The goal isn't to avoid exponential work; it's to avoid exploring branches that produce nothing. This explores only productive nodes, so it's optimal up to the cost of writing the output."

That reframes the complexity as inherent to the problem rather than a weakness in the solution.

5. Java Prerequisites

StringBuilder as backtracking state

sb.append('(');                       // CHOOSE
backtrack(...);                       // EXPLORE
sb.setLength(sb.length() - 1);        // UN-CHOOSE

setLength(len - 1) truncates by one character — the standard undo when building a string during backtracking. deleteCharAt(sb.length() - 1) does the same thing.

Every append before a recursive call needs a matching removal after it. Counting them is the discipline that prevents polluted state. See 15.

Why not String concatenation

backtrack(open + 1, close, n, s + "(", res);     // works, but allocates per node

Strings are immutable, so each + builds a new O(n) string. With exponentially many nodes that's a lot of allocation — though at n <= 8 it's harmless. The StringBuilder version reuses one buffer.

Note the immutable version needs no un-choose, because each recursive call receives its own value. That's a genuine readability advantage, and worth mentioning as a deliberate trade.

sb.toString() materializes a copy

res.add(sb.toString());        // snapshot — safe to keep
res.add(sb);                   // WRONG — stores a reference that keeps mutating

Adding the builder itself would store a live reference, and every stored "result" would end up identical. toString() copies, which is exactly the same hazard as new ArrayList<>(path) in list-based backtracking.

List.of for an immutable base case

if (n == 0) return List.of("");      // Java 9+, immutable singleton

Note this returns a list containing the empty string, not an empty list. List.of("") has size 1; List.of() has size 0 — and the closure recursion depends on the former.

6. Interview Communication Guide

Clarifying questions

1. "Does the output order matter?" — no, any order is accepted, so I don't need to sort or generate in a particular sequence.
2. "Only round brackets, or multiple types?" — only () here; multiple types would change the state I have to track.
3. "Should I return the strings themselves, or just the count?" — the strings. If only the count were needed, it's the Catalan number in O(n) with no enumeration at all.
4. "How large can n be?" — 8, which is the signal that exponential output is expected.
5. "Can n be 0?" — constraints say n >= 1, but n = 0 would conventionally give [""].

The pitch

"First, the constraint: n is at most 8. That's tiny, and it tells me exponential output is expected — the number of valid strings is the Catalan number, 1430 at n = 8. So there's no polynomial algorithm to find; the question is how much wasted work I do.

The naive approach generates all 4^n strings of length 2n and filters. At n = 8 that's 65,536 candidates for 1430 answers — 98% discarded.

Instead I'll build strings by backtracking, and only ever make choices that can't produce an invalid string. Two rules: I can add ( while open < n, and I can add ) only while close < open.

That second rule is the whole correctness argument. A bracket string is valid exactly when the closers never exceed the openers at any prefix, and the totals match at the end. close < open enforces the first at every step, and stopping at length 2n forces the second. So every leaf is valid by construction — I never write a validity check, because invalid states are unreachable.

Complexity is the Catalan number times O(n) to build each string, so O(4^n / √n). That's optimal, since just writing the output costs that much."

Edge cases to raise proactively

Worth volunteering: the count is the Catalan number, and I'd sanity-check my output size against it — 1, 2, 5, 14, 42, …. If my solution returned 6 for n = 3 I'd know immediately I was generating duplicates or invalid strings.

Also worth saying: the first character must always be (, since close < open fails when both are 0. That's a good confirmation the rules are doing their job.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "Just return the count of valid strings, not the strings themselves."

Then you don't enumerate at all — it's the n-th Catalan number, C(n) = (2n)! / ((n+1)! · n!), computable in O(n) with the iterative form C(n) = C(n−1) · 2(2n−1)/(n+1). That's a collapse from exponential to linear, purely because the output shrank from all the strings to one number. Watch for overflow — C(35) already exceeds int.

"What if n could be 20 or more?"

Enumeration is impossible — C(20) is about 6.6 billion strings. If they truly want them all, the only option is to generate lazily: an iterator producing the next valid string on demand, so memory stays O(n) even though the full sequence is unbounded in practice. If they want the count, the Catalan formula handles it instantly.

"Multiple bracket types — (), [], {} — all well-formed."

The state grows from two counters to a stack of which types are currently open, because a closer must match the most recent opener. That's Valid Parentheses's structure used during generation. The count grows substantially, since each pair now has three type choices.

"Generate only strings with a given maximum nesting depth."

Add depth to the recursion state: incremented on (, decremented on ), with the ( branch also requiring depth < maxDepth. One extra condition on Rule 1 — a good demonstration that the "make invalid states unreachable" approach extends cleanly to new constraints.

"Given a string with some brackets already fixed, complete it."

The same backtracking, but at each position check whether it's pre-filled. If so, verify that character is legal under the two rules and recurse without branching; otherwise branch as normal. Pre-filled characters prune the tree heavily.

"Return them in lexicographic order."

The backtracking already does it, if ( is explored before ) — since '(' < ')' in ASCII, the natural DFS order is lexicographic. Worth checking rather than adding a sort: recognizing that the traversal order already satisfies the requirement saves an O(C(n) · n log C(n)) sort.