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.
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
def subsets(nums): # LeetCode 78
res, path = [], []
def dfs(i):
if i == len(nums): # decided every number
res.append(path[:]) # record a copy
return
path.append(nums[i]) # choose: take nums[i]
dfs(i + 1) # explore with it
path.pop() # un-choose
dfs(i + 1) # explore without it
dfs(0)
return res
def permute(nums): # LeetCode 46
res, path, used = [], [], set()
def dfs():
if len(path) == len(nums): # every number placed
res.append(path[:])
return
for x in nums:
if x in used: # already on the path
continue
path.append(x); used.add(x) # choose
dfs() # explore
path.pop(); used.remove(x) # un-choose
dfs()
return res
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".
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".
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.
| Problem | Time | Space | Why | Last 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 |
| Subsets | O(n · 2ⁿ) | O(n) | Two branches per number, so 2ⁿ leaves; copying each subset costs up to n. | not run yet |
| Permutations | O(n · n!) | O(n) | n choices, then n − 1, … so n! leaves; copying each costs n. | not run yet |
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.
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.
Stop at the first success and pass True back up; the path holds the answer.
Never stop early: record a copy at every complete leaf, then un-choose and keep going.
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