Permutations with a used set
Pick any unused element next; undo the pick when you return.
used[] marks exactly the elements in the current path.
01The intuition
Start with what you would do by hand
Three runners, 1, 2 and 3, finish a race. List every possible finishing order. By hand: 123, 132, 213, 231, 312, 321. Six orders. You likely did it by fixing who came first, then who came second among the rest. Count it that way: 3 choices for first, then 2 for second, then 1 left:
3 × 2 × 1 = 6, and n × (n − 1) × … × 1, called n factorial, in general
With five runners that is 120 orders and the by-hand method starts to slip; with eight, 40,320. The pattern is the "fix first, then the rest" idea written so a computer never repeats and never forgets.
Build the structure, one piece at a time
Piece one: a path, the order built so far, a stack you push onto and pop from.
Piece two: a used array, one yes/no per runner, saying whether that runner is already in the path. Without it you would have to scan the path every time to see who is still free.
Piece three: the rule, solve(): if the path has all n runners, record a copy. Otherwise, for each runner r with used[r] = no, in order: mark used[r] = yes, push r, call solve(), pop r, mark used[r] = no. Then move to the next r.
| path | used (1,2,3) | next action |
|---|---|---|
| [] | n n n | choose 1 |
| [1] | y n n | choose 2 |
| [1, 2] | y y n | choose 3 |
| [1, 2, 3] | y y y | record 123, pop 3 |
| [1, 2] | y y n | no other free runner, pop 2 |
| [1] | y n n | choose 3 |
| [1, 3] | y n y | choose 2, record 132 |
| [] | n n n | after undoing 1, choose 2 first: 213, 231, then 3 first: 312, 321 |
Each level of the recursion decides one position in the order; the recursion tree has n branches at the top, n − 1 below, and so on down to n factorial leaves.
Why it is correct
The invariant: used[r] is yes exactly when r is in the path. Both are changed together, mark-and-push on the way down, pop-and-unmark on the way up, so it never breaks. Because of it, each level picks only runners not already placed, so a recorded path is a genuine order with no repeats. Because the loop tries every free runner at every level in a fixed order, every order is produced, and produced once: two different orders differ at some first position, and the loop at that level tries the two runners in separate branches.
Why it is fast
The leaves number n factorial, and each leaf copies a path of length n:
work ≈ n × n factorial
The used array makes each "is this runner free?" check constant time instead of a scan of the path, which would add another factor of n.
How to recognise it in an interview
Cues: "all orderings", "all arrangements", "every permutation", or a small n (up to about 9) where items must be placed one per position. The first thing to say: "I will backtrack with a used array, choosing any unused element for the next position." Permutations is the example above. Permutations II has repeated values: sort, and at each level skip a value equal to the previous one if that previous copy is currently unused, so equal runners are placed in one canonical order. Letter Combinations of a Phone Number is the same loop shape with one position per digit and the digit's letters as the choices.
02The idea in one line
Pick any unused element next; undo the pick when you return.
Reach for it when: Permutations, permutations II, next permutation, permutation sequence.
Cost: O(n · n!) time.
03The walk-through, step by step
The video works one example: Permutations of [1,2,3]. These are its captions in order, so you can follow without the video or check a step you missed.
- Pick any unused number next; undo the pick when you return
- Choose 1: mark used, push on the path
- Choose 2: mark used, push on the path
- Choose 3: mark used, push on the path
- Path full: record 123
- Choose 3: mark used, push on the path
- Choose 2: mark used, push on the path
- Path full: record 132
- Undo 1: unmark it, pop, try the next unused
- Choose 2: mark used, push on the path
- Choose 1: mark used, push on the path
- Choose 3: mark used, push on the path
- Path full: record 213
- Choose 3: mark used, push on the path
- Choose 1: mark used, push on the path
- Path full: record 231
- Undo 2: unmark it, pop, try the next unused
- Choose 3: mark used, push on the path
- Choose 1: mark used, push on the path
- Choose 2: mark used, push on the path
- Path full: record 312
- Choose 2: mark used, push on the path
- Choose 1: mark used, push on the path
- Path full: record 321
- Undo 3: unmark it, pop, try the next unused
- All 3! = 6 orders produced, none repeated
- n choices, then n−1, …: O(n · n!)
04Asked at Google
6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Letter Combinations of a Phone Number | Medium | 58 | last 6 months |
| Permutations | Medium | 49 | last 6 months |
| Permutation Sequence | Hard | 36 | last 6 months |
| Permutations II | Medium | 31 | last 6 months |
| Beautiful Arrangement | Medium | 21 | last 6 months |
| Strobogrammatic Number II | Medium | 17 |
05Related patterns
Other patterns in Backtracking: Subsets (include / exclude), Combination sum with a start index, Grid DFS with undo, Constraint placement with pruning, Generate valid sequences.