# Backtracking

## Remarks

- The backtracking algorithm solves the optimization problem by incrementally building out candidate solutions and backtracks a candidate as soon as we can determine it will not leads to optimal.
- If we represent the partial solutions as a tree, backtracking is doing depth-first search in this tree.
- Since it explores all of the tree in worst case, its upper bounded to have exponential time complexity. It usually need some constraints to prune the tree.
- Very often we would pass both the candidate solution as well as the state of partial solution to the recursive call to speed up checks. Or in some cases, we can mark the problem space to indicate candidate, so that we don’t need to carry the history around.

### Template

To find one solution

```
def backtrack(candidate, state):
if criterion(candidate, state): return candidate
for choice in choices:
if not constraints(candidate, state, choice): continue
result = backtrack(expand(candidate, state, choice))
if result: return result
return
solution = backtrack(init_candidate, init_state)
```

To collect all possible solutions

```
solutions = set()
def backtrack(candidate, state):
if criterion(candidate, state): return solutions.add(candidate)
for choice in choices:
if not constraints(candidate, state, choice): continue
backtrack(expand(candidate, state, choice))
backtrack(init_candidate, init_state)
```