Backtracking

Backtracking is a way to search through all possible solutions by building them one choice at a time. As soon as a partial solution cannot possibly work, you undo the last choice and try the next option. It is like solving a maze with a piece of chalk: walk forward, and at a dead end, go back to the last junction and take a different path.

In this lesson you will learn the general backtracking template, use it to list subsets and arrangements, add pruning to skip hopeless branches, and finish with the classic N-Queens puzzle.

The template: choose, explore, unchoose

Almost every backtracking solution has the same shape:

def backtrack(path, options):
    if path is a complete solution:
        save a copy of path
        return
    for choice in options:
        if choice is allowed:
            path.append(choice)      # choose
            backtrack(path, ...)     # explore
            path.pop()               # unchoose (backtrack)

That is pseudocode, not runnable Python, but every example below follows it. The path.pop() line is the "back" in backtracking: it restores the state exactly as it was before the choice, so the next choice starts clean.

Generating all subsets

A canteen offers four extras with a meal: papad, raita, salad and pickle. How many different combinations can a student pick, including none? For each extra there are two choices, take it or leave it, so there are 2⁴ = 16 subsets.

def subsets(items):
    result = []
    path = []

    def explore(i):
        if i == len(items):              # decided about every item
            result.append(path[:])       # save a COPY
            return
        path.append(items[i])            # choice 1: take items[i]
        explore(i + 1)
        path.pop()                       # undo the choice
        explore(i + 1)                   # choice 2: skip items[i]

    explore(0)
    return result

all_meals = subsets(["papad", "raita", "salad", "pickle"])
print(len(all_meals))
for meal in all_meals[:5]:
    print(meal)

16
['papad', 'raita', 'salad', 'pickle']
['papad', 'raita', 'salad']
['papad', 'raita', 'pickle']
['papad', 'raita']
['papad', 'salad', 'pickle']

The recursion tree has two branches at each of the n levels, so there are 2ⁿ leaves and the time is O(n × 2ⁿ) (copying each subset costs up to n). Exponential time is unavoidable here, because the output itself has 2ⁿ items.

Generating permutations

A permutation is an ordering. Three friends, Aarav, Priya and Kabir, can sit in a row in 3! = 6 ways. To build an ordering, choose who sits in the first seat from everyone not yet seated, then fill the next seat, and so on. A used list remembers who is already seated.

from itertools import permutations

def arrangements(people):
    result, path = [], []
    used = [False] * len(people)

    def explore():
        if len(path) == len(people):
            result.append(" ".join(path))
            return
        for i, person in enumerate(people):
            if not used[i]:
                used[i] = True
                path.append(person)
                explore()
                path.pop()
                used[i] = False

    explore()
    return result

seats = arrangements(["Aarav", "Priya", "Kabir"])
print(len(seats), seats)

# The standard library does the same for you
print(len(list(permutations(["Aarav", "Priya", "Kabir"]))))

6 ['Aarav Priya Kabir', 'Aarav Kabir Priya', 'Priya Aarav Kabir', 'Priya Kabir Aarav', 'Kabir Aarav Priya', 'Kabir Priya Aarav']
6

Permutations grow even faster than subsets: n! orderings, so 10 people already give 36,28,800 arrangements. In real code, use itertools.permutations() and itertools.combinations() when you just need them. In interviews you are usually asked to write the backtracking yourself, often with an extra rule that lets you prune.

Pruning: stop early

Backtracking becomes powerful when you prune: you check the partial solution and abandon a branch as soon as it cannot lead to an answer. Meera has a ₹1,000 gift voucher and wants items whose prices add up to exactly ₹1,000. If the items are sorted by price, the moment a price takes the total over the budget, every later (more expensive) item will too, so the loop can stop.

def exact_baskets(prices, budget, prune=True):
    prices = sorted(prices)
    found, path = [], []
    checks = 0

    def explore(start, remaining):
        nonlocal checks
        if remaining == 0:
            found.append(path[:])
            return
        for i in range(start, len(prices)):
            checks += 1
            if prices[i] > remaining:
                if prune:
                    break                 # sorted: the rest are too expensive
                continue
            path.append(prices[i])
            explore(i + 1, remaining - prices[i])
            path.pop()

    explore(0, budget)
    return found, checks

prices = [650, 150, 400, 250, 100, 350, 600, 200, 450, 300]
baskets, checks = exact_baskets(prices, 1000)
print(len(baskets), "baskets, for example", baskets[:3])
print("Prices checked with pruning:", checks)
print("Prices checked without pruning:", exact_baskets(prices, 1000, prune=False)[1])

18 baskets, for example [[100, 150, 200, 250, 300], [100, 150, 300, 450], [100, 150, 350, 400]]
Prices checked with pruning: 234
Prices checked without pruning: 401

Passing i + 1 as the new start means each item is used at most once and each basket is found in only one order. Both versions find the same 18 baskets, but with pruning the search looks at 234 prices instead of 401, because break skips every item that is even more expensive. On bigger inputs, good pruning is often the difference between a few milliseconds and several minutes.

Advanced: the N-Queens puzzle

Place N queens on an N by N chessboard so that no two attack each other: no two in the same row, column or diagonal. Place one queen per row. For each row, try every column, and only continue if the square is safe. Three sets make the safety check O(1): used columns, used "down" diagonals (squares on one have the same row - col) and used "up" diagonals (same row + col).

def solve_queens(n):
    cols, down, up = set(), set(), set()
    placement = []                       # placement[row] = column
    solutions = []

    def place(row):
        if row == n:
            solutions.append(placement[:])
            return
        for col in range(n):
            if col in cols or (row - col) in down or (row + col) in up:
                continue                 # attacked: prune this branch
            cols.add(col); down.add(row - col); up.add(row + col)
            placement.append(col)
            place(row + 1)
            placement.pop()
            cols.remove(col); down.remove(row - col); up.remove(row + col)

    place(0)
    return solutions

for n in [4, 6, 8]:
    print(n, "queens:", len(solve_queens(n)), "solutions")

first = solve_queens(6)[0]
for col in first:
    print(" ".join("Q" if c == col else "." for c in range(6)))

4 queens: 2 solutions
6 queens: 4 solutions
8 queens: 92 solutions
. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .

The unchoose step has to undo everything the choose step did: the column, both diagonals and the placement. Forgetting one of them is the most common backtracking bug.

Common mistakes

• Saving path instead of a copy. result.append(path) stores the same list object every time, and after all the pops every saved entry is empty. Save path[:].
• Not undoing every change. Each change in the choose step needs a matching undo.
• Pruning on unsorted data. The break trick only works if later options are guaranteed to be worse.
• Using backtracking when a formula or DP exists. If you only need a count, Dynamic Programming is often much faster.

Key points

• Backtracking builds solutions one choice at a time and undoes choices that cannot work.
• The template is choose, explore, unchoose; save a copy of the path when it is complete.
• Subsets take O(2ⁿ) and permutations O(n!), because there are that many answers.
• Pruning abandons hopeless branches early and is what makes backtracking practical.
• Sets give O(1) safety checks, as in N-Queens with columns and two kinds of diagonals.

def make_codes(length):
    result, path = [], []

    def explore():
        if len(path) == length:
            result.append("".join(path))
            return
        for letter in "ABC":
            if path and path[-1] == letter:
                continue                     # prune: same as the neighbour
            path.append(letter)
            explore()
            path.pop()

    explore()
    return result

print(len(make_codes(3)), len(make_codes(6)))
print(make_codes(3))

12 96
['ABA', 'ABC', 'ACA', 'ACB', 'BAB', 'BAC', 'BCA', 'BCB', 'CAB', 'CAC', 'CBA', 'CBC']