🎓 A1Learner
🔍
0 of 112 lessons completed

DSA The Backtracking Template

Backtracking is a search method that builds one answer step by step and undoes a step when it leads nowhere. The partial answer kept during the search is called the path.

Choose and unchoose

Choosing appends one value to the path. Unchoosing pops it, and the path returns to its old state.

path = []
path.append("A")
print("after choose:", path)
path.append("B")
print("after choose:", path)
path.pop()
print("after unchoose:", path)
path.pop()
print("after unchoose:", path)

A two-step decision tree

Two steps with two options each give four complete paths. The paths print in the order the search grows them.

def grow(path, depth, results):
    if depth == 2:
        results.append("".join(path))
        return
    for pick in ("0", "1"):
        path.append(pick)
        grow(path, depth + 1, results)
        path.pop()

results = []
grow([], 0, results)
print(results)
print("paths:", len(results))

Pruning a branch early

Pruning means cutting a branch before it is complete. A branch that already breaks a rule is never grown further.

calls = [0]

def grow(path, results):
    calls[0] += 1
    if len(path) == 3:
        results.append("".join(path))
        return
    for pick in ("0", "1"):
        if path and path[-1] == "1" and pick == "1":
            continue
        path.append(pick)
        grow(path, results)
        path.pop()

results = []
grow([], results)
print(results)
print("paths:", len(results))

Example

def grow(path, results, depth):
    label = "".join(path) if path else "(root)"
    print("  " * depth + label)
    if len(path) == 3:
        results.append("".join(path))
        return
    for pick in ("0", "1"):
        path.append(pick)
        grow(path, results, depth + 1)
        path.pop()

results = []
grow([], results, 0)
print("all paths:", results)
print("count:", len(results))
print("2^3 =", 2 ** 3)

Key points

  • Backtracking builds answers one choice at a time along a path.
  • The template has three moves.
  • Choose, explore, then unchoose.
  • Choosing adds one option to the path.
  • Unchoosing removes it again, so the next option starts clean.
  • A search ends a branch when the path is complete or breaks a rule.

In this example, the template grows every binary string of length 3. Each line of the tree shows one path, indented by its depth. The choose step appends a digit, and the unchoose step pops it after the branch returns. Eight complete paths print at the end. The count matches 2^3, so no branch was lost or repeated.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A backtracking search has just finished exploring one choice. What must happen before the next choice is tried?