Permutations
A permutation is an ordering of all the items: abc, acb, bac... Subsets asked in or out? per element. Permutations ask what comes next? per position, and an item may not be reused.
The backtracking shape survives, with one addition: a used array so a branch never picks the same item twice.
- At each level, loop over every unused item.
- Choose it (
used[i] = True, append), recurse, then undo both marks.
There are n choices, then n-1, then n-2... so n! leaves (3! = 6, 10! ≈ 3.6 million). Permutation backtracking is only viable for small n, and interviewers expect you to say so.
Code exercise · python
Run this. The for loop inside explore is the new ingredient: every unused character gets its turn at the current position, with a full choose/explore/undo around it.
Quiz
How many permutations does a 10-item list have?
Pruning: cut branches early
Backtracking's saving grace is that you can prune: if a partial path already breaks the rules, skip the entire subtree under it with a continue. No descendant of an invalid prefix can ever become valid.
if path and abs(path[-1] - nums[i]) <= 1: continue # this branch is already doomed
Pruning does not change the worst-case Big-O, but in practice it can cut millions of nodes. Every famous backtracking problem (N-queens, sudoku, word search) is "enumerate + prune aggressively". State the prune out loud in interviews, it is the part that earns points.
Quiz
subsets (lesson 6-1) needed no used array, but permutations does. Why?
Code exercise · python
Your turn. Count permutations of nums where every adjacent pair differs by MORE than 1. Start from the permutations skeleton, and prune any choice that lands next to a too-close neighbor.
Problem
In backtracking, a partial path already violates the problem's rules. What do you do with that branch of the decision tree, in one word?