What is backtracking?

Trial-and-error search method.

What is backtracking?

Backtracking searches by trial and error. At an infeasible step it returns and tries another path.

It walks the solution space like a tree; pruning speeds it up and cuts unnecessary branches.

Backtracking is often used for N-queens, sudoku and maze solving; thanks to its flexibility.

Trial and error

Backtracking takes a step, checks if it can proceed. If yes it deepens; if no it returns.

This is implemented naturally with recursion; each call is a step.

Thanks to recursion, backtracking happens automatically; the call stack holds the state.

Exercise Generate subsets

Write subsets(arr). Generate all subsets of an array with backtracking. Print [[], [1], [2], [1, 2]] with print(subsets([1, 2])).

Show example solution

def subsets(arr):
    # Generate subsets
    result = []
    def backtrack(start, path):
        result.append(list(path))
        for i in range(start, len(arr)):
            path.append(arr[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result
print(subsets([1, 2]))

Test yourself

When does backtracking return?
- Every step
- When a step is infeasible
- Never
- Only at the start
Show answer

When a step is infeasible — When a step is infeasible.
Recursion base
```
if len(path) == ____:
```
Show answer
```
if len(path) == n:
```
What is backtracking: match the terms

backtrack

Return
try

Try
undo

Undo
prune

Prune

Next lesson: State tree

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies