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

graph.png

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 END
        • FindPath( 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…

  1. We will need to keep track of the original set, which I will call baseSet (that's { A, B, C }).
  2. We will need to keep track of all possible results, so a set of sets.
  3. We will need to build a permutation at a time (before it goes into the results set), so our current permutation.
  4. 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 used list.

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 our permutation.
  • 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 permutation vector.

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:

  1. 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:

  1. GetAllPermutations( {} ) – Just showing the WIP permutation here
  2. GetAllPermutations( {'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…

  1. GetAllPermutations( {} )
  2. GetAllPermutations( {'A'} )
  3. GetAllPermutations( {'A', 'B'} )
  4. 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:

  1. GetAllPermutations( {} ) – Just showing the WIP permutation here
  2. GetAllPermutations( {'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:

  1. GetAllPermutations( {} )
  2. GetAllPermutations( {'A'} )
  3. 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:

  1. GetAllPermutations( {} )
  2. GetAllPermutations( {'A'} )
  3. GetAllPermutations( {'A', 'C'} )
  4. 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();
        }
    }
}

Author: RachelWil

Created: 2026-10-14 Wed 11:12

Validate