Editor

Permutations with backtracking in Python

Backtracking builds every arrangement of the letters by choosing a letter, filling the remaining places the same way, then undoing the choice so the next letter can take that place.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. path holds the letters chosen so far, and used[i] says whether letters[i] is already in it.
  2. For each letter that is not used yet, choose it: mark it in used and add it to path. Then call permute to fill the remaining places.
  3. When path is as long as letters, one full arrangement is saved in results.
  4. After the call returns, undo the choice with path.pop() and used[i] = False, so the next letter can be tried in that place. That undo is the backtracking.

What to watch

  • Watch every permute frame point at the same path and used lists: there is only one of each, changed and then restored.
  • Watch the call stack grow to four permute frames when path is full, then shrink as the search backs up.
  • Watch results gain a new arrangement each time the stack is at its deepest.

The code

letters = "abc"
results = []

def permute(path, used):
    if len(path) == len(letters):
        results.append("".join(path))   # a full arrangement
        return
    for i in range(len(letters)):
        if used[i]:
            continue                    # already in path
        used[i] = True                  # choose
        path.append(letters[i])
        permute(path, used)             # explore
        path.pop()                      # un-choose: backtrack
        used[i] = False

permute([], [False] * len(letters))
print(results)
Output
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Open it in the editor · Python Program to Print All Permutations of a String, explained