Where it runs
1. The problem
You have three errands: bank, post office, pharmacy. You want to try every order you could run them in. In some orders you reach the bank before it closes. In others you don't. With three errands there are 6 orders, easy to write out. With eight errands there are 40,320, far too many to hold in your head.
You need a method that lists every possible order of a set of items, one at a time. It misses none and repeats none. An order that uses all the items is called a permutation. Three items give 6 permutations, four give 24. From there the count climbs very fast. It is written n! and read "n factorial": for three items it is 3 × 2 × 1, for four it is 4 × 3 × 2 × 1.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- generate all subsets/permutations/combinations
- n is small (roughly n <= 12-20), exponential search is acceptable
- make a choice, recurse, then undo it before trying the next choice
- place items under constraints and back off on conflict (N-Queens, Sudoku)
- return every valid arrangement, not just one
Looks similar, isn't
- Recursion
Recursion goes down and comes back. Backtracking also puts the state back as it returns.
- Recursion with memoization
A cache pays off when arguments repeat. Down a path of distinct choices they rarely do.
- Dynamic programming (1-D)
DP counts or optimises without listing anything. Backtracking is for when you need the arrangements.
- Matrix word search (grid DFS/backtracking)
That is this pattern on a grid. The choice there is which neighbour to step into.
The output is exponential, so n stays small. Subsets of 20 items are 1e6, permutations of 10 are 3.6e6.
On LeetCode
Problems that list every ordering of a set of items. Keep a used flag per item, add any unused one, recurse, then take it back.
The lesson task under the same name.
Sort, and at one level skip a value equal to the previous one that is not in use, so equal values never swap places.
Count the letters, then on each level try each letter that still has copies left, and count every nonempty path.