The Decision Tree

The Idea

Backtracking is depth-first search over a tree you never build. Each node is a partial answer, each edge is one choice, and each leaf is a finished candidate.

The loop is always the same three moves: push a choice onto the path, recurse to extend it, then pop it off. That pop is the whole trick — it restores the path so the next option starts from exactly the same state, which is why one list can serve the entire search.

Real-World Example

Trying keys on a ring of unlabelled keys in a building with several locked doors. You take a key, walk deeper, and when a door refuses you put that key back before trying the next one — otherwise the ring is wrong for every attempt after.

The Code

def walk(options, path, out):
    if len(path) == 2:               # the decision sequence is complete
        out.append("".join(path))
        return
    for opt in options:
        path.append(opt)             # choose
        walk(options, path, out)     # explore
        path.pop()                   # un-choose

out = []
walk(["a", "b"], [], out)
print(out)

out = []
walk(["a", "b"], [], out)
print(out)