Course contentsShow
← Computer Science
Lesson 858 of 2,87220. Recursion Patterns and TechniquesFree lesson

Generating All Permutations

Building all permutations of a set by swapping elements and backtracking through choices.

Generating All Permutations

What you'll learn: How to use backtracking to generate every possible ordering of a set of elements by systematically swapping and undoing swaps.

The Core Idea

A permutation is a specific arrangement of items. If you have three letters—A, B, C—there are 6 permutations: ABC, ACB, BAC, BCA, CAB, CBA. Generating all permutations means producing every possible ordering.

The backtracking approach works by making choices, exploring what happens with each choice, then undoing that choice to try the next option. Think of it like trying on different outfits: you put on shirt A, try all pants, then take off shirt A and try shirt B with all pants.

The Swapping Strategy

Start with your elements in an array. At each position (left to right):

  1. Choose: Swap the current position with each remaining element (including itself)
  2. Explore: Recursively generate permutations for the rest of the array
  3. Unchoose (Backtrack): Swap back to restore the original state

When you reach the end of the array, you've built one complete permutation—record it!

Why It Works

By systematically swapping each element into each position and backtracking, you explore every possible arrangement exactly once. The swapping lets you "fix" one element in place while recursively permuting the others. When you backtrack (undo the swap), you restore the array to try a different choice at that position.

This is the backtracking template pattern in action: make a choice, recurse, then undo that choice.

Key Takeaway: Generating permutations uses backtracking by swapping elements into each position, recursively permuting the remaining elements, then swapping back to explore other arrangements—systematically building every possible ordering.