Backtracking

No. 07 · SVG · Hedge mazetree maze · recursion · subsets · permutations

Drag across the maze. Click it, then use ← → to step and Space to play.

Backtracking is recursion that keeps a trail. You explore one path; when it hits a dead end, you undo the last choice and try another. Every call follows the same three beats: choose (add a step to the path), explore (recurse), un-choose (pop it off again). The pop is what makes it backtracking: when a call returns, the path is exactly as it was before that call made its choice, so the next option starts clean.

FIG. 7 · A tree drawn as a hedge maze. Gates marked 0 are walls. The path list is a thread laid in the channel below the board: every append pulls a gate down into it, every pop winds it back. Red is where the code is now; hatched dashed gates were tried and given up. Callouts: A root, B leaf, C depth.

Step 1 / 1
READY
Nodes visited
Path
Backtracks
Result
Codeleaf_path
def leaf_path(root, path):         # path from root to a leaf, no zeros
    if not root or root.val == 0:  # dead end
        return False
    path.append(root.val)          # choose
    if not root.left and not root.right:
        return True                # reached a leaf
    if leaf_path(root.left, path) or leaf_path(root.right, path):
        return True                # explore
    path.pop()                     # un-choose (backtrack)
    return False

Examples

Backtracking · LeetCode 78

All subsets of [1, 2, 3]. Each level of the decision tree is one number: take it or skip it. Every leaf is a finished subset, so there are 2³ = 8. Trigger: "all subsets", "all combinations".

O(n · 2ⁿ) timeO(n) space2ⁿ leaves, each copied in O(n); path and stack are n deep (output not counted)
Backtracking · LeetCode 46

All orderings of [1, 2, 3]. Each level places one more number that is not used yet: 3 choices, then 2, then 1, so 3! = 6 leaves. Trigger: "all permutations", "all arrangements".

O(n · n!) timeO(n) spacen! leaves, each copied in O(n); path, used and stack are n deep

Time and space

n is the number of nodes (tree maze) or of input numbers (subsets, permutations); h is the tree height. The last column fills in when a run finishes.

ProblemTimeSpaceWhyLast run on the bench
Tree maze (leaf_path)O(n)O(h)Each node is entered at most once. The path and the call stack hold one root-to-leaf route.not run yet
SubsetsO(n · 2ⁿ)O(n)Two branches per number, so 2ⁿ leaves; copying each subset costs up to n.not run yet
PermutationsO(n · n!)O(n)n choices, then n − 1, … so n! leaves; copying each costs n.not run yet

Why the maze is linear but subsets are exponential

In a tree maze the choices are already drawn: each node is a fixed place, entered at most once, so the work is O(n). In subsets and permutations the tree is not given; it is every possible sequence of choices, and the answer asks for all of its leaves. The tree itself has exponentially many nodes, so no amount of cleverness gets below listing them. Pruning (stopping a branch as soon as it can't work) is how real problems keep this in check.

Backtracking vs plain recursion

Plain recursion (page 3) builds an answer from what calls return. Backtracking also carries shared state, the path, that every call changes on the way in and must restore on the way out. Forget the pop and the path keeps stale steps from branches that already failed.

Trigger words: when the problem wants backtracking

Find one way

  • does a valid path exist
  • find the path

Stop at the first success and pass True back up; the path holds the answer.

Find them all

  • all combinations
  • all subsets
  • all permutations

Never stop early: record a copy at every complete leaf, then un-choose and keep going.

Template

def leaf_path(root, path):         # path from root to a leaf, no zeros
    if not root or root.val == 0:  # dead end
        return False
    path.append(root.val)          # choose
    if not root.left and not root.right:
        return True                # reached a leaf
    if leaf_path(root.left, path) or leaf_path(root.right, path):
        return True                # explore
    path.pop()                     # un-choose (backtrack)
    return False