Stop 20 · Data Structures & AlgorithmsTopics · 5/8

Recursion & Backtracking

In short

Generate every subset, solve a Sudoku, place N queens: these sound scary until you see they're one small pattern. Choose, explore, undo. Learn it once and a whole family of questions opens up.

Solving problems by having a function call itself on smaller subproblems, with backtracking exploring and undoing choices to search a solution space.

The purple blob stands at a dead end in a hedge maze, holding a ball of string that trails back.

Think of it like this

The hedge maze at a mela

In a mela maze you hold a ball of string. At each fork you pick a path and keep walking. Dead end? Wind the string back to the last fork and try the next turn. Walking deeper is recursion. Winding back and undoing your last choice is backtracking.

Watch it happen

Every subset of [a, b]

start []

take a [a]

skip a []

take b [a,b]

skip b [a]

take b [b]

skip b []

1/5First choice: take 'a'. The path is now [a]. Go one level deeper.

The big ideas

What you need to know

Base case first

Every recursive function needs a stopping point. Without it, Python raises RecursionError after about 1000 calls.

Each call is a fork

A recursive call is one choice at a fork. The call stack remembers where to come back to.

Choose, explore, undo

Backtracking adds a choice, recurses, then removes the choice so the next branch starts clean.

Prune early

If a partial answer already breaks a rule, return straight away. Pruning is what makes backtracking fast enough.

See it in code

Walk through the code

python

1def subsets(nums):2    result, path = [], []3 4    def backtrack(i):5        if i == len(nums):          # base case: no choices left6            result.append(path[:])7            return8        path.append(nums[i])        # choose9        backtrack(i + 1)            # explore with it10        path.pop()                  # undo11        backtrack(i + 1)            # explore without it12 13    backtrack(0)14    return result15 16print(subsets(["a", "b"]))  # [['a', 'b'], ['a'], ['b'], []]

1/3Base case: every item is decided, so save a copy of the current path.

The take-or-skip template. Swap the base case and the choices and the same shape solves permutations, combination sum and word search.

Save yourself the pain

Common mistakes

Oops

Saving result.append(path) instead of a copy.

Do this instead

path keeps changing. Save path[:] or list(path), or every answer will end up as the same empty list.

Oops

Forgetting to undo the choice after the recursive call.

Do this instead

Every append before recursing needs a matching pop after it, so sibling branches don't see leftover choices.

Your mission

The backtracking trio

~45 min

Quick check

Your subsets function returns [[], [], [], []] for [a, b]. What's the most likely bug?

Go deeper

1Practice classic backtracking problems: permutations, subsets, combinations.
2Learn to identify the base case and recursive case clearly before coding.
3Trace recursion trees by hand for a few problems to build intuition.