Interactive Explainer

Relevant for:Mid-levelSeniorPrincipal

Why this matters at your level

Mid-level

Implement combination sum, permutations, and subsets using the backtracking template. Know the choose-recurse-unchoose pattern cold. Understand when pruning applies and how to identify the pruning condition for a given problem.

Senior

Recognise when backtracking will blow up exponentially in production. Know how to add memoisation to convert backtracking into dynamic programming. Understand constraint propagation for problems like Sudoku and N-queens.

Principal

Design systems that avoid backtracking in hot paths. Know when SAT solvers or constraint satisfaction libraries are more appropriate than hand-rolled backtracking. Understand the connection between backtracking and NP-completeness.

Backtracking

How to systematically explore all possible solutions to a problem, trying options and undoing choices when they lead to dead ends. The algorithm behind Sudoku solvers, chess engines, and permission systems — and how Slack's permission resolution became exponentially slow when employees accumulated many roles.

~4 min read

Be the first to complete!

LIVEAPI Slowdown — Slack — Permission Resolution, 2018

Breaking News

Enterprise growth

Large enterprise customers configure complex role hierarchies — some accounts accumulate 30+ roles with permission inheritance

Permission check

API calls invoking permission resolution for complex accounts take 20-30 seconds instead of milliseconds

CRITICAL

User impact

Slack API returns 504 timeout; users see blank channel sidebar or cannot send messages in affected workspaces

CRITICAL

Investigation

Engineering identifies O(2^n) permission path explosion — exponential in number of inherited roles

WARNING

Fix deployed

Memoisation added: cache permission result per role — each unique subproblem solved once, O(n) replaces O(2^n)

—API response time for enterprise accounts — versus 2ms for regular users with few roles

—complexity reduction after memoisation — same logic, cached intermediate results

The question this raises

When you need to explore every possible combination of choices, how do you stop the exponential blowup from making the program unusable?

Test your assumption first

You are writing code to generate all valid 4-digit PINs where no digit repeats. Your first solution generates all 10,000 possible 4-digit combinations and filters out the ones with repeated digits. A colleague says this is inefficient. Why?

What you'll learn

Backtracking explores all possible options by building solutions incrementally and abandoning paths that cannot lead to a valid solution
The template: choose an option, recurse with the reduced problem, then undo your choice (unchoose) before trying the next option
Pruning is the key optimisation: detect invalid paths early and stop exploring them — can shrink the search space from exponential to tractable
Backtracking is O(2^n) or O(n!) in the worst case — always look for pruning opportunities or memoisation to reduce this
When memoised backtracking is applied to overlapping subproblems, it becomes dynamic programming
Classic problems: N-queens, Sudoku, word search in a grid, generate all subsets or permutations or combinations summing to a target

Lesson outline

What this looks like in real life

The lock combination problem

You forgot the last 3 digits of a 6-digit combination. You remember the first 3 are 4-2-7. You try 4-2-7-0-0-0, fail. Then 4-2-7-0-0-1, fail. Eventually finding 4-2-7-3-8-1. That is brute force. Backtracking adds a rule: if you know from the lock mechanism that any combination with 9 in position 4 is impossible, you skip all 100 combinations starting with 4-2-7-9 immediately. That pruning is the entire power of backtracking.

Backtracking Template

choose → recurse → unchoose
Prune invalid paths early
Base case: complete valid solution

Use for: Reach for backtracking when you need ALL valid combinations or permutations, or when you need to find ANY valid assignment that satisfies constraints (Sudoku, N-queens, word search)

The insight that makes it work

The key insight: you do not explore the whole search tree — you detect dead ends and prune entire subtrees. A Sudoku board has 9^81 possible fills, but backtracking solves it in milliseconds by noticing after 3 digits that a row already contains a 5 and refusing to explore any further path that places a 5 in that row.

How this concept changes your thinking

Situation

Before

After

I need to generate all permutations of [1, 2, 3]

“I try all possible arrangements by brute force — seems like I need to enumerate n! combinations by hand”

“Backtracking: place 1 first, recurse for remaining [2,3]. Then backtrack (undo), place 2 first, recurse for [1,3]. The undo step removes the placed number, restoring the array for the next option.”

I need to solve a Sudoku puzzle

“I try every possible number in every cell — 9^81 possibilities, runs for millions of years”

“I place a digit only if it does not violate row or column or box constraints. If a cell has no valid digit, I backtrack immediately. Most branches are pruned after 1-2 digits.”

I need all subsets of a set

“I loop through every possible subset — feels like I need to check 2^n combinations one by one”

“Backtracking: at each element, branch into "include it" and "exclude it". The recursive structure generates all 2^n subsets without manual bookkeeping.”

Walk through it in plain English

Backtracking: find all combinations of [1,2,3] that sum to 4

→

Start with empty combination, target remaining = 4. We can include any number from [1,2,3].

→

Try including 1. Remaining target = 4-1 = 3. Recurse with [1] selected, using numbers ≥1 to avoid duplicates.

→

Try including 1 again. Remaining = 3-1 = 2. Recurse with [1,1]. Try including 1 again: remaining = 2-1 = 1.

→

Try including 1 once more. Remaining = 1-1 = 0. Found solution: [1,1,1,1]. Add to results.

→

Backtrack. Remove the last 1. Remaining back to 1. Try including 2: 1-2 = -1, overshot — prune this branch. Try 3: 1-3 = -2, overshot — prune. Backtrack again.

→

Continue exploring other starting points. After exhausting all paths starting with 1, try starting with 2. Eventually find [1,3] and [2,2] as additional solutions.

Notice the pruning. [3,1] is never generated because we only use numbers ≥ the last chosen number. This halves the search space by avoiding duplicate combinations in different orderings.

Start with empty combination, target remaining = 4. We can include any number from [1,2,3].

Try including 1. Remaining target = 4-1 = 3. Recurse with [1] selected, using numbers ≥1 to avoid duplicates.

Try including 1 again. Remaining = 3-1 = 2. Recurse with [1,1]. Try including 1 again: remaining = 2-1 = 1.

Try including 1 once more. Remaining = 1-1 = 0. Found solution: [1,1,1,1]. Add to results.

Backtrack. Remove the last 1. Remaining back to 1. Try including 2: 1-2 = -1, overshot — prune this branch. Try 3: 1-3 = -2, overshot — prune. Backtrack again.

Continue exploring other starting points. After exhausting all paths starting with 1, try starting with 2. Eventually find [1,3] and [2,2] as additional solutions.

Notice the pruning. [3,1] is never generated because we only use numbers ≥ the last chosen number. This halves the search space by avoiding duplicate combinations in different orderings.

Now in code

The backtracking template — combination sum. Every backtracking function has the same skeleton: base case, loop over choices, choose, recurse, unchoose. The unchoose step is what makes it backtracking rather than plain recursion.

backtracking.py

1def combination_sum(candidates: list, target: int) -> list:
2    results = []
3 
4    def backtrack(start: int, current: list, remaining: int):
5        if remaining == 0:                          # base case: valid solution
6            results.append(list(current))           # copy current state
list(current) creates a copy. If you append current directly, every entry in results points to the same list, which is empty when the function returns. This is the number one bug in backtracking implementations.
7            return
8        if remaining < 0:                           # pruning: overshot
Pruning: if remaining < 0, we have overshot and no deeper path can fix it. Return immediately without going deeper. This single check eliminates entire subtrees.
9            return
10 
11        for i in range(start, len(candidates)):
12            current.append(candidates[i])           # choose
start=i (not start+1) allows re-using the same number. Use start+1 if each element can only be used once. This single parameter controls the entire branching behaviour.
13            backtrack(i, current, remaining - candidates[i])  # recurse
current.pop() is the unchoose step. It must execute whether or not the recursive call found a solution. Without it, current keeps growing and you explore corrupted state.
14            current.pop()                           # unchoose (backtrack)
15 
16    backtrack(0, [], target)
17    return results

The trap — what most people try first

The two most common backtracking bugs: forgetting to copy the current list when adding to results (all results end up empty), and forgetting the unchoose step (state accumulates incorrectly across branches).

Missing copy and missing unchoose

Bug

# BROKEN: two critical mistakes
def backtrack_broken(candidates, target):
    results = []
    current = []
    def explore(start, remaining):
        if remaining == 0:
            results.append(current)   # BUG 1: reference, not copy
            return
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            explore(i, remaining - candidates[i])
            # BUG 2: missing current.pop() — no backtracking
    explore(0, target)
    return results  # all entries are [] at the end

Fix

# CORRECT: copy on success, pop on exit
def backtrack_fixed(candidates, target):
    results = []
    current = []
    def explore(start, remaining):
        if remaining == 0:
            results.append(list(current))  # copy current state
            return
        if remaining < 0:
            return                         # prune overshoot
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            explore(i, remaining - candidates[i])
            current.pop()                  # undo choice
    explore(0, target)
    return results

The first bug means every entry in results points to the same current list, which is empty when the function finishes — so results ends as a list of empty lists. The second bug means current grows without bound and never correctly represents the current path. Both bugs are invisible in tests that only check if a solution was found at all — they appear when you verify the actual content of results.

When to reach for this

Do you need ALL valid combinations, permutations, or subsets?

YesUse backtracking — build solutions incrementally, prune invalid branches early

NoContinue...

Do you need ANY valid assignment that satisfies hard constraints (Sudoku, N-queens)?

YesUse backtracking with constraint propagation — prune as soon as a constraint is violated

NoContinue...

Are subproblems repeated (same sub-combination computed multiple times in the tree)?

YesAdd memoisation — memoised backtracking becomes dynamic programming, O(n²) instead of O(2^n)

NoConsider greedy — if making the locally best choice is always globally safe

How fast is it?

Scenario	What happens	Speed
All permutations of n items	Every arrangement explored — n! paths	Very slow (O(n!))
All subsets of n items	Each item included or excluded — 2^n paths	Slow (O(2^n))
Backtracking with pruning (Sudoku, N-queens)	Invalid branches cut early — tiny fraction of all possibilities explored	Fast in practice despite O(2^n) worst case
Backtracking + memoisation (repeated subproblems)	Each unique subproblem solved once — becomes dynamic programming	Fast (O(n²) or polynomial)

Exam Answer vs. Production Reality

1 / 1

Backtracking

📖 What the exam expects

Backtracking is recursive exhaustive search: build a solution incrementally, prune paths that cannot succeed, and undo choices when you backtrack. Template: choose, recurse, unchoose. Worst case is O(2^n) or O(n!). Pruning and constraint propagation make it tractable in practice.

Toggle between what certifications teach and what production actually requires

How this might come up in interviews

Backtracking problems share a fingerprint: "generate all valid X" or "find any valid assignment satisfying constraints". Classic forms: generate all permutations, all subsets, all combinations summing to K, all valid parentheses, solve N-queens, solve Sudoku, word search in a grid. The problem often sounds like it needs a nested loop but actually needs recursive enumeration.

Common questions:

Combination sum (I and II — with and without duplicate elements)
Permutations (basic and with duplicates)
Subsets (power set)
N-queens
Word search in a grid

Strong answer: identifies the problem as backtracking by recognising "all valid X" pattern / states the three-part template (choose-recurse-unchoose) before writing code / mentions the copy-on-success bug proactively / adds pruning as a natural part of the solution / connects to DP when asked about further optimisation

Red flags: appends current list reference instead of copying it / forgets the unchoose step (current.pop()) / cannot identify what the "choices" are at each recursive step / does not mention pruning / writes generate-all-and-filter instead of prune-before-recursing

🧠Mental Model

💡 Analogy

Imagine solving a maze. At each junction you try the left path. If you hit a dead end, you backtrack to the last junction and try the right path instead. You carry a trail of breadcrumbs showing where you have been — and when you backtrack, you pick up the breadcrumbs. Eventually you either reach the exit (found a valid solution) or exhaust all paths (no solution exists). Backtracking is systematic maze-solving: try, fail, undo, try again.

⚡ Core Idea

Backtracking is recursive exhaustive search with early exit. You build a candidate solution step by step. At each step, if the current partial solution cannot possibly lead to a valid complete solution, you stop and try something else. The "undo" step is what separates backtracking from plain recursion: you must restore state to exactly what it was before the failed choice so the next branch gets a clean slate.

🎯 Why It Matters

Many real-world problems have no polynomial-time algorithm — you must explore all possibilities. Backtracking makes this tractable by pruning: instead of trying every combination (n!), you cut branches the moment you detect they cannot work. Sudoku has 6.7 × 10^21 possible grids but backtracking solves any valid puzzle in milliseconds because invalid paths are detected and pruned after placing 2-3 digits.

Ready to see how this works in the cloud?

Switch to Career Paths for structured paths (e.g. Developer, DevOps) and provider-specific lessons.

View role-based paths

Discussion

Questions? Discuss in the community or start a thread below.

Join Discord