Backtracking
When order matters
Every item available at every level, and a marker to stop reusing the same one.
Key idea
No start index, a used marker instead
When different orderings are different answers, the start index goes away: every item is a candidate at every level. What replaces it is a record of which items are already placed in the current arrangement.
A boolean list parallel to the items is the usual form. It is set before the recursive call and cleared after it, which is the undo step applied to something other than the result being built.
What the marker buys you is that the pool of candidates shrinks as you descend. Below is one path straight down the tree, taking the first available item at every level, with no recursion in sight.
Why it works
Two things chosen means two things undone
Each iteration changes two pieces of state: the arrangement being built and the used markers. Both have to be restored, and forgetting either produces a distinctive failure.
Forgetting the pop gives arrangements that keep growing. Forgetting to clear the marker gives far too few results, because items stay permanently consumed after the first branch that used them.
Whenever a search touches more than one piece of shared state, count the changes and count the restorations before running it.
Tip
The in-place alternative
There is a second standard formulation that permutes the list in place by swapping the current position with each later one, recursing, and swapping back. It uses no extra list and no markers.
It is shorter and its duplicate handling is harder to reason about, which matters in the next lesson. Either is a good answer; know that both exist and pick one deliberately.
Cost
The cost
There are n factorial arrangements and each costs O(n) to copy, so O(n times n factorial) time. The used list and the recursion depth are both O(n), so the space beyond the output is O(n).
That factorial is why these problems always have tiny constraints. Seeing n at most 8 or so in a problem statement is a strong hint that an exponential or factorial search is expected, which is the constraints-as-a-hint idea from Unit 0 doing real work.
Find the missing restoration
This is meant to produce every ordered pair of different items. On three items it returns two results instead of six. Click the line where a restoration is missing.
This activity type is not wired up yet.
Permutations
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.