Table of Contents
Backtracking algorithms are another form of recursive problem solving where each recursive call adds on another "step" into a list of steps to take to solve the original program. If we hit a road-block on one of the solutions (i.e., the path we're on is not viable), then we backtrack, abandoning that "path" of steps, and continuing on so that a collection of all valid solutions is returned.
1. Example: Finding a path
Let's say we have a graph of nodes and we want to get from "A" to "F". We look at each node one at a time. The following isn't actually code, just a representation of the path building.
FindPath( A )FindPath( A -> B )FindPath( A -> C )
At the node A we have two choices: Go to B or C, so we recurse in each direction. As we take a path, it will keep track of each step it has taken so far. We keep moving to the next Node until we hit a dead end or the goal location.
FindPath( A )FindPath( A -> B )FindPath( A -> B -> D )FindPath( A -> B -> D -> E )– DEAD ENDFindPath( A -> B -> D -> F )– SOLUTION
FindPath( A -> C )– DEAD END
2. Backtracking: Get all permutations
Let's say we have a set of characters and we want to find all possible permutations - all possible orders the set's elements can come in.
- The set
{ A }can only be written that way. - The set
{ A, B }can be written{ A, B }or{ B, A }. - The set
{ A, B, C }can be written{ A, B, C },{ A, C, B },{ B, A, C },{ B, C, A },{ C, A, B },{ C, B, A }.
That's just me, a human, figuring that out. But how do we write an algorithm to do it? We will need a few things to keep track of…
- We will need to keep track of the original set, which I will call
baseSet(that's{ A, B, C }). - We will need to keep track of all possible
results, so a set of sets. - We will need to build a permutation at a time (before it goes into
the
resultsset), so our currentpermutation. - And we will need to track, for the permutation we're actively building,
if we've used a given element in the set yet or not. This will be our
usedlist.
Our terminating case will be if the permutation we're currently
working on matches the baseSet size - they're two sets of the
same length - then that means we've built a full set. At this point
we can add our WIP permutation to the list of results and return.
For the recursive case, we will iterate over all of the elements
of the baseSet ({ A, B, C } as the example). We have our
array of used markers which just have "true" or "false" for each
index.
Within the for loop, we check if used[i] is false. If it's false,
then we are adding it to our work in progress permutation:
- Set
used[i]to true, - then push
baseSet[i]onto ourpermutation. - We then recurse, calling GetAllPermutations again with our same data.
- After the function call, we set
used[i]to false again, - then pop this item out of the back of the
permutationvector.
2.1. What will this look like to step through?
2.1.1. Base call
Our first call to GetAllPermutations will have these values:
baseSets |
{ 'A', 'B', 'C' } |
permutation |
{} |
used |
{ 0, 0, 0 } |
results |
{} |
Call stack:
GetAllPermutations( {} )– Just showing the WIP permutation here
Our WIP permutation is empty, so we're not hitting the terminating case.
With the for loop, we start at index 0. This item ('A') isn't used,
so we add it to our WIP permutation (now {'A'}). Then we call
GetAllPermutations again.
2.1.2. Recursing
baseSets |
{ 'A', 'B', 'C' } |
permutation |
{ 'A' } |
used |
{ 1, 0, 0 } |
results |
{} |
Call stack:
GetAllPermutations( {} )– Just showing the WIP permutation hereGetAllPermutations( {'A'} )
Skip terminating case.
For loop: used[0] is now "true", so we move to the next one.
baseSet[1] is 'B'. We set used[1] to true, push baseSet[1]
to the WIP permutation (now {'A', B'}), then call
GetAllPermutations again.
We'll skip ahead a little…
GetAllPermutations( {} )GetAllPermutations( {'A'} )GetAllPermutations( {'A', 'B'} )GetAllPermutations( {'A', 'B', 'C'} )
The first permutation built is the same as the original baseSet.
{'A', 'B', 'C'} gets pushed into our results and the latest
call is returned.
Let's go back to GetAllPermutations( {'A'} ).
Within the for loop
we don't do anything for i=0 because that's 'A', and we just
went through i=1 for adding 'B' as the second item.
Parameters:
baseSets |
{ 'A', 'B', 'C' } |
permutation |
{ 'A' } |
used |
{ 1, 0, 0 } |
results |
{ {'A', 'B', 'C'} } |
Call stack:
GetAllPermutations( {} )– Just showing the WIP permutation hereGetAllPermutations( {'A'} )
Our for loop is at i=2 now, so we're going to add 'C' to the
WIP permutation (now { 'A', 'C' }) then call GetAllPermutations
again.
Parameters:
baseSets |
{ 'A', 'B', 'C' } |
permutation |
{ 'A', 'C' } |
used |
{ 1, 0, 1 } |
results |
{ {'A', 'B', 'C'} } |
Call stack:
GetAllPermutations( {} )GetAllPermutations( {'A'} )GetAllPermutations( {'A', 'C'} )
For loop again. i=0 is skipped because we're using 'A' already,
i=1 will then add 'B' to our permutation and call GetAllPermutations.
Parameters:
baseSets |
{ 'A', 'B', 'C' } |
permutation |
{ 'A', 'C', 'B' } |
used |
{ 1, 1, 1 } |
results |
{ {'A', 'B', 'C'} } |
Call stack:
GetAllPermutations( {} )GetAllPermutations( {'A'} )GetAllPermutations( {'A', 'C'} )GetAllPermutations( {'A', 'C', 'B'} )
Our WIP permutation length matches our baseSet length so we've found
another solution, which will be added to the results.
And so on it goes. It might help to step through it on paper to fully see how the algorithm goes and get a feel for it.
void GetAllPermutations( vector< vector<char> >& results, vector<char>& baseSet, vector<char>& permutation, vector<bool>& used ) { if ( baseSet.size() == permutation.size() ) { results.push_back( permutation ); return; } for ( size_t i = 0; i < baseSet.size(); i++ ) { if ( used[i] == false ) { used[i] = true; permutation.push_back( baseSet[i] ); GetAllPermutations( results, baseSet, permutation, used ); used[i] = false; permutation.pop_back(); } } }