Lesson 9 of 16

Backtrack from Impossible Choices

Generating every complete combination wastes time extending choices that already fail. Backtracking builds a partial answer and returns as soon as it violates a condition.

Match a sum of positive numbers

Choose distinct positive numbers from [2, 4, 5], each at most once, to total 6. At each item, include it or skip it. Once the total exceeds 6, adding more positive numbers cannot help.

numbers, target = [2, 4, 5], 6
answers = []

def search(index, total, path):
    if total == target:
        answers.append(path.copy())
        return
    if total > target or index == len(numbers):
        return
    path.append(numbers[index])
    search(index + 1, total + numbers[index], path)
    path.pop()
    search(index + 1, total, path)

search(0, 0, [])
print(answers)

The output is [[2, 4]]. An append records a choice; pop undoes it after that branch finishes. This keeps the exclusion branch free of the earlier choice. Copying the path when saving an answer also protects it from later changes.

Pruning needs justification

The code relies on positive numbers. With negatives, a total above the target might later decrease. The same pruning rule could then discard a valid answer.

In a queens-placement puzzle, sharing a column or diagonal with an existing queen rules out a candidate. DFS determines exploration order; backtracking rejects candidates using constraints. DFS can implement a backtracking search.

Pruning may reduce work, but the worst case can still explore nearly every subset. The number of search nodes is O(2^n), with additional cost for copying and storing answers. The recursive path itself uses O(n) space.

Check your understanding

If -3 may appear later, can you stop immediately when the current total is 8 and the target is 5?