The General Pattern

Characteristics of backtracking algorithms

Backtracking algorithms are commonly used to make a sequence of decisions, with the goal of building a recursively defined structure satisfying certain constraints. Often (but not always), this goal structure is itself a sequence. For example:

• In the $n$ queens problem, the goal is a sequence of queen positions, one in each row, such that no two queens attack each other. For each row, the algorithm decides where to place the queen.
• In the game tree problem, the goal is a sequence of legal moves, such that each move is as good as possible for the player making it. For each game state, the algorithm decides the best possible next move.
• In the $SubsetSum$ problem, the goal is a sequence of input elements that have a particular sum. For each input element, the algorithm decides whether to include it in the output sequence or not.

(Hang on, why is the goal of subset sum finding a sequence? That was a deliberate design decision. We imposed a convenient ordering on the input set by representing it using an array, as opposed to some other more amorphous data structure that we can exploit in our recursive algorithm.)

In each recursive call to the backtracking algorithm, we need to make exactly one decision, and our choice must be consistent with all previous decisions. Thus, each recursive call requires not only the portion of the input data we haven’t yet processed, but also a suitable summary of the decisions we have already made. For the sake of efficiency, the summary of past decisions should be as small as possible. For example: