# Combinatorial search

## Backtracking

• A systematic way to run through all the possible configurations of a search space.
• Configurations
• permutations := all possible arrangements of objects
• subsets := all possible ways of building a collection of them
• enumerating all spanning trees of a graph, all paths between two vertices, or all possible ways to partition vertices into color classes
• We must generate each possible configuration exactly once.
• At each step in the backtracking algorithm, we try to extend a given partial solution $a = (a_1, a_2, …, a_k)$ by adding another element at the end. After this extension, we must test whether what we now have is a complete solution: if so, we should print it or count it. If not, we must check whether the partial solution is still potentially extendable to some complete solution.