Permutations¶
Also known as: Backtracking (Permutations), Arrangements
Same machinery as subsets, but now order matters, so at each step you pick any unused element rather than just deciding yes or no on the current one. The "used" bookkeeping is the whole difference.
Before you start¶
What 'solved properly' looks like
Target: O(n! × n). If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
At each recursion level, you loop through every element in the input, but you skip any that are already marked as used. You add the current element to a growing arrangement, mark it used, recurse, then unmark it — that unmarking is the backtrack. The difference from subsets is subtle but critical: subsets decided "yes or no" per element, while permutations decides "which unused element next," which produces every possible ordering.
Why it matters: It's the pattern behind constraint-satisfaction problems like N-Queens, grid word searches, and sudoku — where the real skill is pruning a branch the moment it becomes impossible, rather than exploring it to the bitter end. The "used" bookkeeping is the same structure that carries into graph traversal and DP on subsets.
When to reach for it¶
Reach for it when a problem asks for "all permutations", "all arrangements", or when order clearly matters and the input is small enough that factorial growth is acceptable. Also reach for it when placing pieces under constraints (N-Queens) or searching a grid for a word — those are permutations with pruning.
When not to use it
Factorial growth means n stays small (roughly ≤ 9 before it's hopeless). You must undo the choice on the way back up or state leaks between branches — that's the single most common backtracking bug. And prefer a used boolean array over removing items from a list; removal is O(n) and quietly ruins the complexity.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Permutations | LeetCode | Medium | 20 mins | teaching |
| 2 | Permutations II | LeetCode | Medium | 25 mins | teaching |
| 3 | Word Search | LeetCode | Medium | 30 mins | consolidation |
| 4 | Generate Parentheses | LeetCode | Medium | 25 mins | consolidation |
| 5 | N-Queens | LeetCode | Hard | 45 mins | challenge |
Already know this? Test out.
If you can solve N-Queens cleanly in one sitting — handling the row-by-row placement, the diagonal checks, and the backtracking — you already own this pattern, so move on to the next one. Note this one is Hard and that's the point — it stretches the pattern to its limit. If it doesn't come easily, work the set from the top.