Skip to content

Backtracking

Backtracking is a general algorithm for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate("backtracks") as soon as it determines that the candidate cannot possibly be complated to a valid solution.

It is generally a DFS with proper prune. If current solution is not suitable, then backtrack and try other solutions. Thus, recursion is used in this approach.

The consider process maybe:

  1. Draw a state space tree, where each node represents a state and all its possible sellections are its children;
  2. Determine the terminal condition;
  3. Determine if a pruning is necessary here;
  4. Make selection;
  5. Get into next layer;
  6. Revoke the selection and restore the scene.

A pseudocode can be:

1
2
3
4
5
6
void Backtrack(State& curr) {
  if (is_terminal(curr) || is_prune(curr)) return;
  next = set_state(curr);
  Backtrack(next);
  curr = reverse_state(next);
}

Subsets and Combinations

Subset and combination problems are irrelevant with elements' order, so the problem can be described as: chosing at most m elements that meet the requirement from an array arr, where m is the length of arr. To prevent from choosing one element twice, only elements behind previous selection will be selected at each step.

And for repeating elements, we sort them at the begining and then choose only one of them at each step.

Permutations

When we talk about permutation, the order matters here. Each step we chose an element from all the rest, so we have to remember all the elements we have chosen and select from the other.

Searching