Backtracking (Permutations)

Backtracking is like trying on outfits. Put on one item, then see if you can finish the rest of the outfit. If you hit a dead end, take that item off — this step is the 'backtrack' — and try something else. Generating every permutation, every possible ordering of a list, works the same way. Place one item in the next open slot, try to fill the rest, then undo it and try the next item instead.

1. 1Keep a 'path', the ordering built so far, and a list of 'remaining' items not yet placed.
2. 2For each remaining item, place it in the path. Then try to fill the rest of the path with what is left, using the same steps again.
3. 3When no items remain, the path is one full permutation. Record it, undo the last placement — the 'backtrack' step — and try the next remaining item instead.

Use it to generate every possible arrangement or combination — permutations, subsets, or puzzle solutions like Sudoku or N-Queens. Use it anywhere you need to explore every branch of choices and drop the ones that do not work out.

• ⚠Forgetting to undo the choice after exploring further — the actual backtrack step. Without it, leftover state leaks into the next branch.
• ⚠Not realizing that n! grows explosively. Permutations of just 10 items already total 3.6 million orderings.