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):
- Choose: Swap the current position with each remaining element (including itself)
- Explore: Recursively generate permutations for the rest of the array
- 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.