Essay
Permutations with backtracking
Generate every ordering of an integer slice by swapping in place, recursing, and restoring the previous state.
- Algorithms
- Go
For a slice with distinct values, a permutation chooses each remaining value for the current position, then solves the same problem for the suffix.
For [1, 2, 3], the result contains six orderings:
[1 2 3] [1 3 2] [2 1 3]
[2 3 1] [3 1 2] [3 2 1]Swap, recurse, restore
At index first, swap every candidate into that position and recurse with first + 1. After the recursive call returns, swap the values back. That final swap is the backtracking step: it restores the state expected by the next branch.
When first reaches the last position, copy the current slice into the result. The copy matters because every branch reuses the same backing array.