Skip to content

Volume ITechnology

4.18.0 — Backtracking: The Pattern ​

Recognition cue. The problem says all, every, generate, enumerate, or asks for combinations, permutations, subsets, partitions, or arrangements. The constraint is small — n up to about 20 for subsets, up to about 10 for permutations — which is the setter telling you an exponential answer is expected.

The move. Build a partial answer one choice at a time. When it is complete, record it. When it cannot possibly work, abandon it. Undo each choice on the way back out.

What backtracking actually is ​

It is depth-first search over a tree that you never build. The tree exists only as the sequence of calls on the stack.

Each node of that imaginary tree is a partial answer. Each edge is one choice. A leaf is either a complete answer or a dead end.

                  []
        /                    \
      [1]                     []          ← choose 1, or do not
     /    \                 /    \
  [1,2]   [1]            [2]      []
   / \     / \           /  \     /  \
[1,2,3][1,2][1,3][1]  [2,3][2] [3]  []   ← eight subsets of {1,2,3}

Once you see the tree, every problem in this chapter is the question what are the branches at each node, and which ones can I refuse to walk down?

The four parts ​

Every backtracking solution has exactly these, in this order. Write them as four separate thoughts.

python
def backtrack(state):
    if is_complete(state):          # 1. BASE CASE
        record(state)
        return

    for choice in choices(state):   # 2. THE CHOICES
        if not allowed(choice):     # 3. THE CONSTRAINT — this is the pruning
            continue
        make(choice)                # 4a. do it
        backtrack(state)            #     recurse
        undo(choice)                # 4b. UNDO — the "backtracking"

The skeleton, line by line. state is the partial answer built so far. is_complete asks whether it is a finished answer, such as a full-length permutation. record saves a copy of it. choices lists the possible next steps from here. allowed rejects a step that breaks a rule, before any work is spent below it. make applies the step to the shared state, the recursive call explores everything that follows from it, and undo takes the step back, so the next choice in the loop starts from exactly the state this call was given.

Part 3 is where all the performance is. Checking validity as you choose prunes an entire subtree. Checking it only on complete answers is brute force wearing a recursion costume, and it is the difference between 8^8 and about 2,000 in N-Queens.

Part 4b is where all the correctness is. Whatever you add before recursing must be removed after. Forget it and state leaks between branches, and the results are quietly wrong.

The three loop shapes, and how to choose ​

This is the decision that confuses people most, so here it is in one place. What differs between problems is only the choices available at each node.

Shape 1 — include or exclude (subsets) ​

At index i, either take nums[i] or do not. Then move to i + 1.

python
def backtrack(i, path):
    if i == len(nums):
        result.append(path[:])      # copy!
        return
    path.append(nums[i])            # take it
    backtrack(i + 1, path)
    path.pop()                      # undo
    backtrack(i + 1, path)          # skip it

Two branches per node, n levels deep → 2^n leaves. Use when each element is independently in or out.

Shape 2 — choose the next element, moving forward (combinations) ​

A loop from a start index, and the recursive call moves the start forward. Order does not matter, so [1,2] and [2,1] are the same answer and only one is generated.

python
def backtrack(start, path):
    result.append(path[:])          # every node is an answer, for subsets
    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(i + 1, path)      # i + 1: never look back
        path.pop()

i + 1 versus i is the whole difference between two problem families. i + 1 means each element is used at most once. Passing i means it can be reused — that is Combination Sum.

Shape 3 — choose any unused element (permutations) ​

A loop over everything, with a used-marker. Order matters, so [1,2] and [2,1] are both answers.

python
def backtrack(path, used):
    if len(path) == len(nums):
        result.append(path[:])
        return
    for i in range(len(nums)):
        if used[i]: continue
        used[i] = True
        path.append(nums[i])
        backtrack(path, used)
        path.pop()
        used[i] = False

n choices, then n−1, then n−2 → n! leaves.

The decision, in one table ​

the problem wantsorder matters?reuse allowed?shape
subsetsnono1 or 2
combinationsnono2, recurse with i + 1
combination sumnoyes2, recurse with i
permutationsyesno3, with a used array

Duplicates: the one rule ​

When the input contains repeated values, you will generate the same answer twice. Sort first, then skip a value that equals its predecessor at the same level of the tree:

python
nums.sort()
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i - 1]:
        continue                    # a sibling already tried this value

i > start, not i > 0. The guard must skip duplicates among siblings — different choices at the same position — not duplicates along the path. Using i > 0 would wrongly forbid [2, 2] when there really are two 2s available.

Say that condition out loud when you write it. It is the single most-missed detail in this chapter.

Copy the result ​

python
result.append(path[:])      # a copy — NOT result.append(path)

path is one shared list that keeps changing. Appending it without copying stores a reference, and by the end every entry in result is the same empty list. In JavaScript, [...path].

This bug produces output that looks the right shape but is entirely wrong, so check for it every time.

Complexity, honestly ​

You cannot beat the size of the output. If a problem asks for all 2^n subsets, the answer alone is exponential.

So the complexity is roughly (number of results) × (cost of building each one):

  • subsets — O(2^n \times n)
  • permutations — O(n! \times n)
  • combination sum — bounded by the tree size, hard to state exactly, and saying so honestly is better than inventing a formula

Pruning does not change the asymptotic bound — it changes the constant, and the constant is everything. N-Queens without pruning tries 8^8 \approx 16.7 million placements; with column and diagonal checks at the moment of placing, it explores about 2,000.

The nine problems ​

#ProblemShapeThe one insight
4.18.1Subsets ★1 or 2Every node of the tree is an answer
4.18.2Combination Sum ★2, reuseRecurse with i, not i + 1
4.18.3Permutations ★3A used-marker instead of a start index
4.18.4Subsets II2Sort, then skip siblings with i > start
4.18.5Combination Sum II2The duplicate skip and i + 1 together
4.18.6Word Search ★gridThe board itself is the visited set
4.18.7Palindrome Partitioning ★2The choice is where to cut
4.18.8Letter Combinations ★per-positionThe branching factor comes from a lookup table
4.18.9N-Queensper-rowName the conflict groups: column, r−c, r+c

★ marks the Blind 75 subset.

The traps on this pattern ​

Forgetting to copy the result. Every entry ends up identical.

Forgetting the undo. State leaks between branches.

i > 0 instead of i > start in the duplicate skip. It removes legitimate answers.

Checking validity only at the leaves. That is brute force. Check at the moment of choosing.

Passing i + 1 when reuse is allowed, or i when it is not. One character, two completely different problems.

Not sorting before the duplicate skip. The skip only works if equal values are adjacent.

What the interviewer will push on ​

"Walk me through your recursion tree for n = 3." Draw it. If you cannot draw it, the code will not be right.

"Where does the pruning happen?" Point at the constraint check and say what subtree it removes.

"What is the complexity?" The output size times the cost per result, and then say that pruning changes the constant rather than the exponent.

"Why i + 1 here and i there?" Reuse allowed or not.

"How do you avoid duplicate answers?" Sort, then skip equal siblings with i > start.

"Could you do it iteratively?" For subsets, yes — start with [[]] and for each element append copies of everything so far with that element added. For the rest, an explicit stack of states, which is messier than the recursion.

One thing to volunteer: name the four parts as you write them — choices, constraint, recurse, undo — and say which of the three shapes you picked and why. That framing is what makes the next backtracking problem easy instead of a fresh puzzle.

Recall

  • Backtracking is DFS over a tree you never build. Each node is a partial answer; each edge is one choice.
  • Four parts: base case · the choices · the constraint (this is the pruning) · make, recurse, undo.
  • Three shapes: include/exclude · loop from a start index (order does not matter) · loop over all with a used-marker (order matters).
  • i + 1 = each element used once. i = reuse allowed. One character apart, two problem families.
  • Duplicates: sort first, then if i > start and nums[i] == nums[i-1]: continue. It is i > start, not i > 0.
  • Copy the path when recording: path[:] or [...path]. Otherwise every result is the same reference.
  • Complexity is output size × cost per result. Pruning changes the constant, not the exponent — and the constant is everything.

Next: 4.18.1 Subsets — the simplest tree in the chapter, and the one to draw before writing anything.

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