State tree

Branch solutions into a tree and walk it.

State tree

Backtracking walks solutions as a tree. Each node is a partial solution, each branch a choice.

Leaves are full solutions; internal nodes are intermediate states and pruning happens here.

The state tree visualizes the solution space; branches are cut early via pruning.

Permutation example

All permutations of an array are built by picking an unused element at each level of the state tree.

For n elements there are n! leaves; each gives a different ordering.

Generating permutations is one of the best known applications of backtracking.

Exercise Generate permutations

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

Show example solution

def perms(arr):
    # Generate permutations
    result = []
    def backtrack(path, used):
        if len(path) == len(arr):
            result.append(list(path))
            return
        for i in range(len(arr)):
            if not used[i]:
                used[i] = True
                path.append(arr[i])
                backtrack(path, used)
                path.pop()
                used[i] = False
    backtrack([], [False] * len(arr))
    return result
print(perms([1, 2]))

Test yourself

Add choice
```
path.____(arr[i])
```
Show answer
```
path.append(arr[i])
```
State tree: match the terms

tree

Tree
node

Partial solution
leaf

Full solution
branch

Choice
What does a leaf represent in the state tree?
- Full solution
- Partial solution
- Start
- Pruning
Show answer

Full solution — Full solution.

Next lesson: Pruning

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies