4.8.4 — Generate Parentheses

LeetCode 22 · Medium · ★ Blind 75

The problem

Given n pairs of brackets, return every well-formed combination.

n = 3  →  ["((()))", "(()())", "(())()", "()(())", "()()()"]
n = 1  →  ["()"]

n is between 1 and 8.

The Plain-English Breakdown

You are given a bucket containing n opening brackets ( and n closing brackets ). Your job is to pull them out one by one and form every possible valid string. A string is valid if every opening bracket has a matching closing bracket in the correct order.

Constraints to note:

• n is tiny (up to 8). This is a massive hint! Whenever you see constraints N \le 12, you should immediately think of Backtracking or Recursion because an exponential time complexity like O(2^N) or O(N!) is expected and perfectly acceptable.

Brute Force Analysis

The naive approach generates all 2^{2n} strings of brackets and filters the valid ones.

• How it works: Think of it like flipping a coin 2n times. Heads is (, Tails is ). You write down every sequence, then run a separate isValid() function on every single one.
• Time Cost: Generating all strings is O(2^{2n}). Checking each string takes O(n) time. Total time: O(n \cdot 2^{2n}).
• Why it fails: For n = 8, that is a length of 16. 2^{16} = 65,536 strings. 65,536 \times 16 \approx 1,000,000 operations. It's fast enough to pass n = 8, but absolutely wasteful. It misses the point of the problem entirely by generating hot garbage like ))))(((( which we know from the very first character is doomed to be invalid.

The pattern

Despite sitting in the stack group, this is not a stack problem. It is the first backtracking problem in the book — build a partial answer, extend it in every legal way, and undo each choice on the way back out.

The naive approach generates all 2^{2n} strings of brackets and filters the valid ones. For n = 8 that is 65,536 strings, most of them invalid. Wasteful, and it misses the point.

Instead, never build an invalid string in the first place. At each position you have at most two choices, and each has a simple condition:

• Add ( — allowed while you have used fewer than n open brackets.
• Add ) — allowed while the number of closes is strictly less than the number of opens.

That second rule is the whole problem. A string is well-formed exactly when, reading left to right, closes never overtake opens, and the two totals end equal. Enforce it at every step and every string you produce is valid by construction.

ELI5 Analogy: Think of opening brackets ( like people entering a room, and closing brackets ) like people leaving the room. Rule 1: You can't have more than n people enter in total (the room capacity). Rule 2: People can't leave the room if nobody is inside! So, at any given moment, the number of people who have left the room (close_count) can NEVER be greater than the number of people who have entered (open_count). If you obey these two rules at the door, you will never have a ghost leave the room.

The solution

Python

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

        def build(open_count: int, close_count: int):
            if len(current) == 2 * n:            # a complete string
                result.append(''.join(current))
                return

            if open_count < n:                   # can still open
                current.append('(')
                build(open_count + 1, close_count)
                current.pop()                    # undo

            if close_count < open_count:         # can still close
                current.append(')')
                build(open_count, close_count + 1)
                current.pop()                    # undo

        build(0, 0)
        return result

TypeScript

function generateParenthesis(n: number): string[] {
  const result: string[] = [];
  const current: string[] = [];

  function build(open: number, close: number): void {
    if (current.length === 2 * n) {
      result.push(current.join(''));
      return;
    }
    if (open < n) {
      current.push('(');
      build(open + 1, close);
      current.pop();
    }
    if (close < open) {
      current.push(')');
      build(open, close + 1);
      current.pop();
    }
  }

  build(0, 0);
  return result;
}

The four parts of backtracking are all here, and every problem in 4.18 has the same four:

1. A base case — the string is 2n long, so record it and stop.
2. The choices — add ( or add ).
3. The constraint — the if in front of each choice, which is what makes this efficient rather than brute force.
4. The undo — current.pop() after each recursive call, restoring the state so the next choice starts clean.

Do not skip the undo. Without it, current keeps growing across branches and every result is wrong. The rule is: whatever you add before recursing, remove after.

Why one shared list instead of passing strings around? You could write build(current + '(') and skip the undo entirely, since strings are immutable and each call gets its own copy. That is shorter and easier to get right. It also allocates a new string at every node of the recursion tree, which is O(n) work per node. The shared list with an explicit undo is the version that scales, and it is the habit worth building because the harder backtracking problems cannot afford the copies.

''.join(current) at the base case is the only place a string is built.

Code Walkthrough

1. The Setup: We initialize an empty result list to hold the final valid strings, and a current list to act as our working canvas (representing the partial string we are building right now).
2. The Base Case: Inside the build function, we first check if our canvas is full. Since each valid string requires exactly n opens and n closes, its total length will be 2 * n. If it is full, we glue the canvas together into a string (''.join(current)) and lock it into result. Then we return to backtrack.
3. Choice 1 - Add Open: If we haven't used up our n open brackets (open_count < n), we add ( to the canvas, and call build() again, but this time telling the next level that we've used one more open bracket (open_count + 1).
4. Undo Open: When that recursive call finishes and comes back, we MUST remove the ( we just added using current.pop(). This is like erasing a pencil mark so we can try something else.
5. Choice 2 - Add Close: If we have more open brackets than close brackets on the canvas currently (close_count < open_count), it's safe to add ). We append it, recurse down with close_count + 1, and then pop it off when it returns.

Hand Trace

Let's trace the state of current for n = 2 down the first full branch:

Step	current	open	close	Action / Condition
1	[]	0	0	open < 2 → Push (
2	[ ( ]	1	0	open < 2 → Push (
3	[ (, ( ]	2	0	open < 2 is FALSE. close < open → Push )
4	[ (, (, ) ]	2	1	close < open → Push )
5	[ (, (, ), ) ]	2	2	Length is 2 \times 2 = 4. Base case! Save (()).
6	[ (, (, ) ]	2	1	Return to Step 4, pop() the last ).
7	[ (, ( ]	2	0	Return to Step 3, pop() the ). Backtrack continues!

Edge Cases Handled

• n = 1: The recursion instantly hits [ ( ] then [ (, ) ] and returns ["()"].
• The logic naturally prevents any string starting with ) because at the root level, open_count is 0 and close_count is 0, so close < open evaluates to 0 < 0 which is False.

The recursion tree for n = 2

                    ""
                  /
               "("                     open=1
              /    \
          "(("       "()"              open=2 / close=1
            |          |
         "(()"       "()("             close=1 / open=2
            |          |
        "(())"      "()()"             ← both complete

Notice what is missing: there is no branch starting with ), because close < open is false at the root. The constraint pruned it before it was ever built.

Complexity

The number of valid strings for n pairs is the n-th Catalan number:

C_n = \frac{1}{n+1}\binom{2n}{n}

which grows roughly like 4^n / n^{1.5}. For n = 8 that is 1,430 strings.

Each result costs O(n) to assemble, so the total is O(n \cdot C_n).

The honest way to say this in an interview: "the output is exponential in size, so the algorithm must be at least exponential — but the pruning means we only ever visit valid partial strings, never invalid ones." That sentence is worth more than reciting the Catalan formula. It also names the general truth about enumeration problems: when the answer is a list of every possibility, the complexity is dominated by the size of the output, not by cleverness.

Derivation:

• Time Complexity: O(\frac{4^n}{\sqrt{n}}). At each step, we have 2 choices. A completely unpruned tree of depth 2n would have 2^{2n} = 4^n nodes. However, our constraint prunes many branches. The mathematically exact number of valid strings is the n-th Catalan number, which is bounded by \frac{4^n}{n\sqrt{n}}. Creating each string takes O(n) time due to .join(). So, Time = O(n \cdot C_n) \approx O(\frac{4^n}{\sqrt{n}}).
• Space Complexity: O(n). The depth of the recursion tree is exactly 2n, meaning there will be at most 2n function calls on the call stack at any given time. The current array also holds at most 2n characters. Thus, space scales linearly with n, excluding the output array.

Where this goes next

This is the template for the whole of 4.18. Every problem there is these four parts with different choices and different constraints:

• Subsets — the choice is "include this element or not", and there is no constraint.
• Permutations — the choice is "which unused element comes next", and the constraint is "unused".
• N-Queens — the choice is which column, and the constraint is no shared row, column or diagonal.
• Word Search — the choice is which neighbour to step to, and the constraint is that the letter matches and the cell is unvisited.

Where the constraint sits decides everything. Checking validity as you make each choice prunes whole subtrees. Checking it only on complete answers is brute force wearing a recursion costume.

What the interviewer will push on

"Why is close < open the right condition?" Because a string is well-formed exactly when closes never overtake opens at any prefix. Enforcing it per step makes every generated string valid.

"What is the complexity?" Catalan-many results, O(n) each. Then the sentence about output size dominating.

"Why not generate everything and filter?" 2^{2n} strings instead of C_n — about 45 times more work at n = 8, and the gap widens fast.

"Why the undo?" The list is shared across branches, so state must be restored before trying the next choice.

"Could you do it iteratively?" Yes, with an explicit stack of partial states, or by building n from n−1 results. Both are messier. Recursion is the natural fit because the problem is naturally a tree.

One thing to volunteer: name the four parts of backtracking as you write them. Choices, constraint, recurse, undo. That framing tells the interviewer you have a method that will work on the next backtracking problem too.

Next: 4.8.5 Daily Temperatures — the first monotonic stack, which is the idea that makes this whole group worth studying.