Where it runs
1. The problem
In the last lessons recursion computed one answer: the size of a folder, a Fibonacci number. Backtracking uses the same self-calls to walk every path and collect an answer on each one. At each step it tries a choice, goes deeper, then undoes that choice and tries the next one. There is one new idea here: that undo, putting everything back the way it was before the next try.
You are shipping a release with three feature flags (switches that turn features of a program on or off). Before it goes out, CI (a system that checks code automatically) has to test the release under every combination of the flags. All off, only the first on, the first and third on, all on, and so on. You need the full list of on-off combinations.
For three flags there are 8 combinations. For ten flags there are 1024. Writing them out by hand is not realistic. Nested loops don't work either: the number of flags changes, and every count would need its own depth of nesting.
You need a function that walks the list and, at every item, tries both answers: leave the item out or put it in. Every path from start to end gives one combination.
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 includedbacktrack([], [1, 2], [])List every sequence of length 2 built from [1, 2]. The loop offers every choice at every level, so a value can repeat.
Recognise 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 subset or every combination of choices, one choice per item. Branch on each item, recurse, then undo the choice before the next branch.
The lesson task exactly, skip or take each number.
Each letter branches into lower case and upper case, while digits have one branch.
Each digit gives three or four branches instead of two, and the path is the word built so far.
Sort first, and when you skip a value, skip all its copies too, so no subset repeats.