← Learn DSA · Lesson 7 of 11
Backtracking
Try a choice, explore, undo it, try the next — and prune early.
The idea
Backtracking is brute force that cleans up after itself. You make a choice, recurse on what remains, then undo the choice before trying the next one. That undo is the whole technique: it lets one shared piece of state stand in for the exponentially many states you would otherwise have to build.
Every backtracking solution has the same four parts:
- A choice — which value goes in this position.
- A constraint — whether the choice is still legal given what came before.
- A goal — how you know a full solution has been reached.
- An undo — restoring state so the next branch starts clean.
Miss the undo and later branches inherit earlier decisions, which produces answers that are wrong in ways that look almost right.
The cost is exponential by nature: you are exploring a tree of possibilities. The only lever that matters is pruning — abandoning a branch the moment it cannot lead to a solution. Checking validity when a candidate is complete makes it hopeless; checking it as each choice is made is what turns an impossible search into a fast one. In N-Queens, that difference is the entire problem.
Where subproblems repeat with the same arguments, memoisation applies and the search collapses into dynamic programming. Where they do not, backtracking is usually the best available.
Walkthrough
Counting arrangements with no two adjacent 1s. Watch a cell get set, the search go deeper, and the cell get restored on the way back out — that restore is the backtrack.
What it costs
- time
- Exponential in the worst case — O(branching^depth), reduced by pruning
- space
- O(depth) for the call stack, plus the shared state being mutated
Pruning does not change the worst case; it changes the case you actually hit. That is why the constraint check belongs at every choice rather than at the end.
When to reach for it
- The problem asks for *all* solutions, or a count of them, rather than one best value.
- Permutations, combinations, subsets, or arrangements under constraints.
- Constraint puzzles — N-Queens, Sudoku, word search on a grid.
- The search space is large but most of it is invalid, so pruning cuts it down quickly.
Rather than the obvious alternative
Dynamic programming
If the same subproblem recurs with the same arguments, memoise and the exponential search collapses to polynomial. Backtracking is for when the states are genuinely distinct — which is usually the case once you are building actual arrangements rather than scoring them.
A greedy choice
Far cheaper when it is correct, and wrong on a small counterexample when it is not. Backtracking is what you fall back to precisely because a locally best choice does not lead to a globally best answer.
BFS over states
Better when you need the *shortest* sequence of choices, since BFS finds it first. Backtracking explores depth-first and would have to search everything to prove a path is shortest.
How to spot it
- The problem says "all", "every", "generate", or "how many ways".
- You are filling positions one at a time and each choice restricts the next.
- A solution is a sequence of decisions rather than a single number.
- Brute force is obvious but most candidates are invalid long before they are complete.
Where it goes wrong
Forgetting to undo
The single most common bug. Without restoring state, the second branch starts from the first branch's leftovers, and the answers are subtly wrong rather than obviously broken.
Collecting references instead of copies
Pushing the working array into a results list stores a reference to something you are about to mutate. Every result ends up identical — usually empty. Push a copy.
Validating only at the leaves
Checking the constraint only once a candidate is complete does the full exponential work. Check as each choice is made and prune immediately.
Generating duplicates from equal elements
With repeated values, the same combination is reached by different paths. Sort first and skip an equal sibling at the same depth.
Try it
Two short checks. They run the same way the practice problems do — write the function, press Run.
Return how many subsets nums has, by choosing include-or-exclude for each element recursively. Do not use a formula.
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| countSubsets([1,2,3]) | three elements | 8 | — |
| countSubsets([5]) | one element | 2 | — |
| countSubsets([]) | empty | 1 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Hints
Stuck? Hints open one at a time, each giving a little more away.
2 hints left
Practise it
- Subsetsmedium
- Word Searchmedium