January 1, 0001

# Backtracking

This algorithm tries to construct a solution to a problem one piece at a time. Whenever the algorithm needs to decide between multiple alternatives to the part of the solution it recursively evaluates every option and chooses the best one.

## How to Win

To beat any non-random perfect information game you can define a Backtracking algorithm that only needs to know the following. - A game state is good if either the current player has already won or if the current player can move to a bad state for the opposing player. - A game state is bad if either the current player has already lost or if every available move leads to a good state for the opposing player.

PlayAnyGame(X, player)
if player has already won in state X
return GOOD
if player has lost in state X
for all legal moves X -> Y
if PlayAnyGame(y, other player) = Bad
return GOOD


In practice, most problems have an enormous number of states not making it possible to traverse the entire game tree.

## Subset Sum

For a given set, can you find a subset that sums to a certain value?

SubsetSum(X, T):
if T = 0
return True
else if T < 0 or X is empty
return False
else
x = any element of X
with = SubsetSum(X \ {x}, T - x)
without = SubsetSum(X \ {x}, T)
return (with or without)


X \ {x} denotes set subtraction. It means X without x.

ConstructSubset(X, i, T):
if T = 0
return empty set
if T < 0 or n = 0
return None
Y = ConstructSubset(X, i - 1, T)
if Y does not equal None
return Y
Y = ConstructSubset(X, i - 1, T - X[i])
if Y does not equal None
return Y with X[i]
return None


## Big Idea

Backtracking algorithms are used to make a sequence of decisions.

When we design a new recursive backtracking algorithm, we must figure out in advance what information we will need about past decisions in the middle of the algorithm.