Patternwise

Backtracking

Choose, explore, un-choose — walk every branch of the decision tree.

Brute force
Same exponential search, but rebuilding lists each call costs extra
With the pattern
O(2ⁿ · n) subsets, O(n! · n) permutations — proportional to output
Extra space
O(n) — recursion depth + current path

In plain English

“Packing a picnic basket by trying combinations: you put an apple in, see what else you could add, then take the apple back out and try without it. Because you always undo your last move before trying the next option, the basket is always in the right state for whatever you try next.”

Why it's fast

Some problems genuinely need every answer (all subsets, all permutations), so exponential output is unavoidable. Backtracking makes it cheap per answer by reusing one mutable path: append, recurse, pop. Pruning (stop when the sum exceeds target, skip duplicate values) cuts whole subtrees before you waste time inside them.

Spot it when the problem says…

  • return all possible subsets / combinations / permutations
  • generate all valid …
  • each number may be used once / unlimited times
  • place n queens / solve sudoku
  • partition a string into …
  • word search in a grid

Visualize

Subsets — walk the decision tree

Return every subset of nums. Each node of the tree is one subset.

∅[]1[1]2[1,2]3[1,2,3]3[1,3]2[2]3[2,3]3[3]

path

[]

result (1)

[]
01/23

Record [] — every node in this tree is a valid subset.

pythonline 4
1def subsets(nums):2    result, path = [], []3    def backtrack(start):4        result.append(path[:])          # every node is an answer5        for i in range(start, len(nums)):6            path.append(nums[i])        # choose7            backtrack(i + 1)            # explore8            path.pop()                  # un-choose9    backtrack(0)10    return result

variables

start
0

How to apply it

  1. 01Define the state: a path list plus a start index (combinations) or used set (permutations).
  2. 02Base case: if the path is a complete answer, record a copy (path[:]).
  3. 03Loop over the next choices: choose (append), explore (recurse), un-choose (pop).
  4. 04Add pruning: break when a sorted candidate already overshoots; skip equal neighbours to avoid duplicates.

Variations you'll meet

Subsets (take / skip tree)

The visualizer's example: every node of the decision tree is an answer.

python
def subsets(nums: list[int]) -> list[list[int]]:    res, path = [], []    def backtrack(start: int) -> None:        res.append(path[:])            # every node is a subset        for i in range(start, len(nums)):            path.append(nums[i])       # choose            backtrack(i + 1)           # explore            path.pop()                 # un-choose    backtrack(0)    return res

Permutations (used set)

Order matters, so every position can take any unused element; no start index.

python
def permute(nums: list[int]) -> list[list[int]]:    res, path, used = [], [], [False] * len(nums)    def backtrack() -> None:        if len(path) == len(nums):            res.append(path[:])            return        for i, x in enumerate(nums):            if used[i]:                continue            used[i] = True            path.append(x)            backtrack()            path.pop()            used[i] = False    backtrack()    return res

Combination Sum (reuse allowed + pruning)

Recurse with i (not i + 1) so a number can repeat; sort and break once a candidate exceeds the remainder.

python
def combination_sum(candidates: list[int], target: int) -> list[list[int]]:    candidates.sort()    res, path = [], []    def backtrack(start: int, remain: int) -> None:        if remain == 0:            res.append(path[:])            return        for i in range(start, len(candidates)):            c = candidates[i]            if c > remain:                break                  # sorted: rest are too big            path.append(c)            backtrack(i, remain - c)   # i, not i+1: reuse allowed            path.pop()    backtrack(0, target)    return res

Duplicates in input

Sort, then if i > start and nums[i] == nums[i-1]: continue (Subsets II, Combination Sum II).

Common mistakes

  • Appending path instead of path[:] — every saved answer ends up as the same (empty) list.
  • Forgetting to pop (un-choose), so the path keeps growing across branches.
  • Using i + 1 vs i vs start wrongly — mixes up reuse, combinations and permutations.
  • Dedup check i > 0 instead of i > start, which wrongly skips valid answers.
  • In grid word search, not restoring the cell after marking it visited.

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved
  1. 01Binary Tree Paths ↗Easy
  2. 02Subsets ↗Medium
  3. 03Permutations ↗Medium
  4. 04Combination Sum ↗Medium
  5. 05Subsets II ↗Medium
  6. 06Letter Combinations of a Phone Number ↗Medium
  7. 07Word Search ↗Medium
  8. 08N-Queens ↗Hard

Think you've got it?

Let the AI interviewer throw a Backtracking problem at you and grade how you explain it.

Mock interview