Overview

Backtracking explores a tree of decisions. At each step you make a choice, recurse to make the rest, and then undo the choice so the next option starts from a clean state. Subsets, permutations, combinations, N-Queens and Sudoku are all walks through such a tree.

The output of these problems is often exponential in size, so the goal is not a polynomial algorithm but an efficient search: generate each candidate exactly once, avoid duplicates, and prune branches early when they cannot possibly succeed. Good pruning is the difference between an instant answer and a timeout.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
All subsetsO(n · 2ⁿ)
All permutationsO(n · n!)
Combinations of size kO(k · C(n, k))

Patterns to recognise

Subsets / combinations

Use it for: Subsets, combination sum, letter combinations.

Loop i from start; recurse with i + 1 (or i if reuse is allowed).

Permutations

Use it for: Permutations, next arrangement, anagram generation.

Loop over all items; skip those already used in the path.

Grid search

Use it for: Word search, N-Queens, Sudoku.

Mark a cell or position as used before recursing and unmark it afterwards.

Code template

Combination Sum — reuse allowed, pruned by sorting
def combination_sum(candidates, target):
    candidates.sort()
    result, path = [], []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])          # copy the current path
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                       # sorted, so the rest are too big
            path.append(candidates[i])      # choose
            backtrack(i, remaining - candidates[i])   # i: reuse allowed
            path.pop()                      # un-choose

    backtrack(0, target)
    return result

Common mistakes

  • Appending the path itself instead of a copy — every saved answer then changes as the path does.
  • Forgetting to undo a choice (pop, unmark) corrupts sibling branches.
  • Skipping duplicates across levels instead of within one level drops valid answers.

Quick check

Three questions on Backtracking. Get all three right to earn +15 XP.

  1. What is the core loop of backtracking?

  2. How many subsets does a set of n distinct elements have?

  3. What is pruning in backtracking?

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Backtracking?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor