Summary - Backtracking

Practice backtracking with a mini N-queens style task.

Summary - Backtracking

Backtracking searches with trial and error, a state tree and pruning. N-queens, permutations and subset sum are examples.

In this mini task you will solve the subset sum problem; combine all steps.

Backtracking systematically walks the solution space; it is a powerful tool for constrained problems.

Exercise Subset sum

Write subset_sum(arr, target). Use backtracking to check if any subset sums to target. Print True with print(subset_sum([3, 34, 4, 12, 5, 2], 9)).

Show example solution

def subset_sum(arr, target):
    # Subset sum exists
    def backtrack(i, total):
        if total == target:
            return True
        if i >= len(arr) or total > target:
            return False
        if backtrack(i + 1, total + arr[i]):
            return True
        if backtrack(i + 1, total):
            return True
        return False
    return backtrack(0, 0)
print(subset_sum([3, 34, 4, 12, 5, 2], 9))

Test yourself

Summary - Backtracking: match the terms

backtrack

Return
prune

Prune
try

Try
undo

Undo
Undo
```
path.____()
```
Show answer
```
path.pop()
```
When does backtracking 'undo'?
- Never
- Every step
- Only at the start
- When deepening fails
Show answer

When deepening fails — When deepening fails.

Next lesson: Project: Overview

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies