Permutations
A permutation is an ordering of all the items, such as abc, acb, and bac.
The question changes shape from lesson 6-1. Subsets asked whether each element was in or out, and permutations ask what comes next at each position, with no item reused.
The backtracking skeleton 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 by setting
used[i] = Trueand appending, recurse, then undo both marks.
Undoing both is the part that gets forgotten. used is shared state exactly like path, so it needs the same discipline.
The size is the real constraint. There are n choices, then n − 1, then n − 2, giving n! leaves, where 3! = 6 and 10! is about 3.6 million.
Permutation backtracking is only viable for small n, and interviewers expect you to say so before writing it.
All permutations of a string
The loop inside explore is the new ingredient.
def permutations(items): result = [] path = [] used = [False] * len(items) def explore(): if len(path) == len(items): result.append("".join(path)) return for i in range(len(items)): if used[i]: continue used[i] = True path.append(items[i]) explore() path.pop() used[i] = False explore() return result print(permutations("abc"))
Output
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
Every unused character gets its turn at the current position, with a full choose, explore, undo cycle around each one.
explore() takes no index argument, because the depth is len(path) and the loop covers all candidates rather than a single element. That is the structural difference from subsets.
if used[i]: continue is what enforces no reuse, and the two undo lines put both pieces of state back before the loop tries the next candidate.
"".join(path) snapshots the path into a string, which serves the same purpose as path[:] in lesson 6-1. Strings are immutable, so no separate copy is needed.
The output is in alphabetical order here only because the input was. The traversal is depth-first over the loop order, so it follows whatever order the items arrive in.
A 10-item list has 10! = 3,628,800 permutations.
The arithmetic is 10 × 9 × 8 × ... × 1, one factor per position, with each position having one fewer candidate than the last.
Factorials outgrow even the 2ⁿ from lesson 6-1, and the comparison is stark. 2¹⁰ is only 1,024, so permutations of 10 items are about 3,500 times more numerous than subsets of 10 items.
It gets worse quickly. 13! is over 6 billion, and 20! is around 2.4 × 10¹⁸, which no amount of hardware makes reachable.
So when a problem needs permutations of more than roughly 10 items, brute-force enumeration is off the table and the intended answer involves structure: dynamic programming over subsets, a greedy rule, or a counting formula that never builds the orderings at all.
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 beneath it with a continue.
The justification is a one-liner worth memorizing: no descendant of an invalid prefix can ever become valid. Adding more items to a path that already violates a constraint cannot repair it.
if path and abs(path[-1] - nums[i]) <= 1: continue
The path and guard comes first because path[-1] would fail on an empty path, and the first position has no previous neighbor to check.
Pruning does not change the worst-case Big-O, and in practice it can cut millions of nodes. A prune near the root of the tree removes a whole factorial-sized region.
Every famous backtracking problem is enumerate plus prune aggressively, including N-queens, sudoku, and word search.
State the prune out loud in interviews, because it is the part that earns points. The enumeration is expected, and the pruning shows you know why the enumeration is affordable.
Because in subsets, level i only ever decides element i, so reuse is impossible by construction, while in permutations any unused item can fill the current position.
The subset tree touches each element at exactly one level. Element 0 is decided at the root, element 1 one level down, and nothing can be picked twice because nothing is offered twice.
The permutation tree chooses among all remaining items at every level. Without used, the same item could occupy two positions and aab would appear as a permutation of abc.
That is also why explore in subsets takes an index and explore in permutations does not. The index was the bookkeeping.
And because used is state shared across branches, it must be un-set on the way back out. That is the same choose, explore, undo discipline as path, applied to a second variable.
A common alternative avoids the array entirely by swapping elements into place or by passing the remaining items as a new list. Both trade some memory or clarity for not having to remember the second undo.
Permutations with a prune
Count the orderings where every adjacent pair differs by more than 1.
def special_perms(nums): count = 0 used = [False] * len(nums) path = [] def explore(): nonlocal count if len(path) == len(nums): count += 1 return for i in range(len(nums)): if used[i]: continue if path and abs(path[-1] - nums[i]) <= 1: continue used[i] = True path.append(nums[i]) explore() path.pop() used[i] = False explore() return count print(special_perms([1, 2, 3, 4])) print(special_perms([1, 2, 3]))
Output
2 0
This is the permutations structure with one line added, the prune, placed right after the used[i] check.
Checking only path[-1] is enough because every earlier adjacent pair was validated when it was appended. The constraint is local, which is what makes the prune cheap.
The undo restores both pieces of shared state, with path.pop() and used[i] = False. Forgetting the second leaves items permanently marked as used and the count comes out as 0.
For [1, 2, 3, 4] only [2, 4, 1, 3] and [3, 1, 4, 2] survive, and for [1, 2, 3] nothing does, since 2 has both 1 and 3 as forbidden neighbors and cannot be placed anywhere.
The prune is doing serious work even at this size. Full enumeration is 24 leaves for four items, and most branches die at depth 2 rather than being built out to completion.
Prune it, skipping the entire subtree with a continue or an early return.
The reason is the invariant from earlier in the lesson. No descendant of an invalid prefix can become valid, so everything below that node is guaranteed to be wasted work.
The saving is proportional to where the prune fires. Cutting at depth 2 of a permutation tree for 10 items discards roughly 8! paths in one step.
Enumeration gives correctness and pruning gives speed, and the two are separable. A solution with no pruning is still right, just slow, which makes pruning a safe thing to add after the skeleton works.
Choose, prune, explore, undo is the full backtracking loop, and you now have both halves of it.