Trees and recursion 0/36

Lesson 2 of 5

Backtracking

Build answers one choice at a time, undo each choice, and cut branches that can no longer succeed.

4,652 words ยท 21 min read

Part 1 of 9 Backtracking

For n=2n = 2 the whole search fits in a picture. It starts from the empty prefix, and at every prefix it tries ( first and ) second.

The search for n=2n = 2. A dashed arrow leads to a character that is refused. Two more refusals are not drawn: a third ( after (() and a third ( after ()(.

At the start ) is refused, and with it the 8 strings that begin with ). After (( a third ( is refused, and the path goes on to (() and to the first answer, (()). The search then goes back to (, the last prefix that still has a character to try, and writes ). After () a second ) is refused, and the path goes on to ()( and to the second answer, ()().

This method is called backtracking. A backtracking search starts from an empty answer and extends it one choice at a time. When everything that follows from a choice has been tried, it goes back to the point before that choice and makes the next one.

The picture of all the choices is the search tree. Its root is the empty answer, and each arrow is one choice. Each node the search reaches is one call and holds a partial answer that breaks no rule. A path ends where its answer cannot be extended: either the answer is complete, or every next choice is refused. Backtracking follows each path to its end before it tries the next one. This order is called depth first.

Refusing a choice cuts off the whole subtree below it: no call is made for a faded prefix in the figure, or for any longer prefix that starts with it. This is called pruning.