Skip to content

Volume ITechnology

4.8.4 — Generate Parentheses ​

LeetCode 22 · Medium · ★ Blind 75

The problem ​

You are given a number n. Return every string made of n opening brackets ( and n closing brackets ) that is well-formed. Well-formed means every ( is closed by a later ), and no ) appears without an open ( before it to close.

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

n is between 1 and 8.

That small limit is a hint. When n is this small, the answer is allowed to grow very fast with n, because the answer is a list of every possibility.

What the problem is really asking ​

Picture building the string one character at a time, left to right. At each step you choose ( or ). Some choices lead to a valid string. Others are doomed. For example, a string that starts with ) can never be fixed.

So the real question is: at each step, which choices are still safe, so that we only ever build valid strings?

There is a simple test. Read a string left to right and count opens and closes as you go. It is well-formed exactly when:

  1. The count of closes never goes above the count of opens at any point, and
  2. At the end, both counts equal n.

Think of people entering and leaving a room. ( is someone walking in, and ) is someone walking out. The room holds at most n people in total over the day. And nobody can walk out of an empty room. If you obey those two rules at the door, every day you record is valid.

The brute force, and where it wastes work ​

Make every string of length 2n out of ( and ), then keep only the valid ones.

python
from itertools import product

def generateParenthesis(n):
    def valid(s):
        balance = 0
        for c in s:
            balance += 1 if c == '(' else -1
            if balance < 0:               # a close with nothing open
                return False
        return balance == 0

    return [''.join(p) for p in product('()', repeat=2 * n) if valid(p)]

There are 2^{2n} such strings. For n = 8 that is 65,536, and only 1,430 of them are valid. Each costs O(n) to check.

The waste in one sentence: it builds strings like "))))((((" all the way to the end, even though the very first character already doomed them.

The idea ​

Build the string step by step, and only ever make a choice that keeps it valid. There are two choices, each with a simple rule.

  • Add ( if fewer than n opens have been used.
  • Add ) if fewer closes than opens have been used. That means there is an open bracket waiting to be closed.

If you follow these rules at every step, every complete string you build is valid. You never need to check anything at the end.

This way of searching has a name: backtracking. You build a partial answer, try each allowed next step, and after exploring a step you undo it so you can try the next one. This is the first backtracking problem in the book. Every problem in 4.18 uses the same four parts:

  1. A finish line. When the answer is complete, record it.
  2. The choices. Here, add ( or add ).
  3. The rule in front of each choice. This is what stops you building doomed answers.
  4. The undo. After exploring a choice, take it back.

The solution ​

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

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

            if open_count < n:                           # (5)
                current.append('(')
                build(open_count + 1, close_count)
                current.pop()                            # (6)

            if close_count < open_count:                 # (7)
                current.append(')')
                build(open_count, close_count + 1)
                current.pop()

        build(0, 0)                                      # (8)
        return result
ts
function generateParenthesis(n: number): string[] {
  const result: string[] = [];                           // (1)
  const current: string[] = [];                          // (2)

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

  build(0, 0);                                           // (8)
  return result;
}

Line by line ​

(1) result collects every finished string.

(2) current is the string being built right now, kept as a list of characters. A list is used because adding or removing the last character of a list takes constant time.

(3) The build function. It is recursive, meaning it calls itself. Each call represents one point in the building process. It is told how many opens and closes have been used so far.

(4) The finish line. A valid string has n opens and n closes, so its length is 2n. When current reaches that length, we join the characters into one string, save it, and return to go back to the previous step.

(5) Choice one: add (. Only allowed if we have used fewer than n opens. We add it, then call build to keep going from this new point, with one more open used.

(6) The undo. When that call returns, every string that starts with our current characters plus ( has been built. Now we remove the (, so current is exactly as it was before line (5). That lets choice two start from a clean state.

Do not skip the undo. Without it, current would keep growing across different branches, and every string after the first would be wrong. The rule is simple: whatever you add before the call, remove after it.

(7) Choice two: add ). Only allowed if more opens than closes have been used, meaning some ( is still waiting to be closed. Same pattern: add, go deeper, undo.

(8) Start with nothing used.

Why one shared list, instead of passing strings? ​

You could write build(current + '(') and skip the undo, because each call would get its own new string. That is shorter and harder to get wrong. But it builds a brand-new string at every step, and copying a string of length up to 2n costs O(n) each time. The shared list with an undo avoids that copying. It is the habit worth building now, because the harder backtracking problems cannot afford the copies.

Trace ​

Here is the full search for n = 2. Each line is one call of build, indented by how deep it is.

build(0,0)  current = ""
  add "("  →  build(1,0)  current = "("
    add "("  →  build(2,0)  current = "(("
      open is 2, so no more "("
      add ")"  →  build(2,1)  current = "(()"
        add ")"  →  build(2,2)  current = "(())"   length 4 → save "(())"
        undo ")"
      undo ")"
    undo "("                current = "("
    add ")"  →  build(1,1)  current = "()"
      add "("  →  build(2,1)  current = "()("
        add ")"  →  build(2,2)  current = "()()"   length 4 → save "()()"
        undo ")"
      undo "("
      close is not less than open, so no ")"
    undo ")"
  undo "("
  close (0) is not less than open (0), so no ")" at the very start

The result is ["(())", "()()"]. Notice that no string ever starts with ). The rule in line (7) blocked it at the very first step, so that whole branch was never built.

Complexity, derived ​

How many answers are there? The number of valid strings with n pairs is called the n-th Catalan number, written C_n:

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

Read \binom{2n}{n} as "2n choose n". It is the number of ways to pick n positions out of 2n, which here means choosing where the opens go. Dividing by n + 1 keeps only the arrangements that are valid. For n = 3 this gives \frac{1}{4} \times 20 = 5, which matches the example. For n = 8 it is 1,430.

Time. Because of the rules, every partial string the code builds can be finished into a valid one. So the work is spread over the valid answers, and each finished answer costs O(n) to join into a string. The total is about O(n \cdot C_n). C_n grows roughly like 4^n divided by n^{1.5}, so this is exponential.

That sounds bad, but there is no way around it. The answer itself is a list of C_n strings, each of length 2n. Any method must at least write them all down. When a problem asks for every possibility, the size of the answer sets the speed limit.

Space. Not counting the answer list, the deepest the recursion goes is 2n calls, and current holds at most 2n characters. So the extra memory is O(n).

Edge cases ​

  • n = 1. The only answer is "()".
  • The first character. It is always (, because line (7) cannot run when no opens have been used.
  • The last character. It is always ), because by then all n opens are used.

Variations you will meet ​

Every backtracking problem in 4.18 is these four parts with different choices and rules.

  • Subsets. The choice is "take this item or skip it". There is no rule.
  • Permutations. The choice is "which unused item goes next". The rule is "unused".
  • N-Queens. The choice is which column to place a queen in. The rule is "no two queens attack each other".
  • Word Search. The choice is which neighbouring cell to step to. The rule is "the letter matches and the cell is not already used".

Where the rule sits decides everything. Checking the rule at each step cuts off whole branches early. Checking it only on finished answers is just the brute force written as recursion.

What the interviewer will push on ​

"Why is close < open the right rule?" A string is well-formed exactly when closes never get ahead of opens at any point. Enforcing it at each step makes every finished string valid.

"What is the time complexity?" Catalan-many answers, O(n) each. Then say that the size of the answer sets the limit.

"Why not build everything and filter?" 2^{2n} strings instead of C_n. For n = 8 that is 65,536 against 1,430, about 45 times more work, and the gap grows fast.

"Why do you need the undo?" current is shared by every branch, so it must be put back before trying the next choice.

"Can you do it without recursion?" Yes, with your own stack of partial strings. It is messier. Recursion fits naturally, because the search is shaped like a tree.

One thing to volunteer: name the four parts of backtracking as you write them: finish line, choices, rule, undo. That 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 group worth studying.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet