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)

Sample Questions