Backtracking: Permutations

Backtracking is a way to build a solution one small step at a time. At each step you make a choice, then try to continue from there. If that choice cannot lead anywhere new, you undo it and try the next option.

A simple way to remember the pattern is three words:

1. Choose — pick an option that is still allowed.
2. Explore — recurse to build the rest of the solution.
3. Un-choose — undo the choice so you can try the next option.

This "choose, explore, un-choose" loop lets one piece of code explore every possibility without forgetting to clean up after itself.

A permutation is just an ordering of items. Given n distinct items, we want to list every possible ordering.

How many are there? For the first position you have n choices, for the second position n − 1 choices, and so on. That gives n × (n − 1) × … × 1 = n! orderings.

For [1, 2, 3] there are 3! = 6 permutations:

[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

We build one permutation in an array called current. A used[] array remembers which numbers we have already placed.

At each position we try every number that is not yet used: we choose it (mark it used and add it to current), recurse to fill the next position, and then un-choose it (remove it and mark it unused) so we can try the next number.

When current is full it is a complete permutation, so we save a copy.

Here is the recursion tree for [1, 2, 3]. Each path from the root down to a leaf is one finished permutation:

Watch the recursion run. The top row shows the available numbers (dimmed once used, highlighted blue when just picked). The middle shows the partial permutation being built. The bottom collects every completed permutation in green. Watch how a red "backtrack" step removes the last choice so the next one can be tried.

The function calls itself once for every choice. The base case (a full current) records one finished permutation.

There are n! permutations, and copying each finished permutation costs O(n), giving O(n · n!) total work. The recursion goes at most n levels deep, and current/used use O(n) space, so the extra space is O(n) (not counting the stored output).

Step through the backtracking process at your own pace. Use the controls to move forward and backward and watch how every ordering is discovered.