The idea
A recursive function solves a problem by calling itself on a smaller one, with a base case that stops the chain.
Backtracking uses recursion to walk a tree of choices: at position pos, try each option, recurse to fill the rest, then undo the option before trying the next. It enumerates permutations, subsets and placements.
The cost is exponential: n! for permutations (fine up to about n = 10), 2ⁿ for subsets (about n = 20). Cutting branches that cannot lead to a valid or better answer (pruning) is what makes it usable.
Sample problem
47. Permutations II ↗ Medium
Given a list of numbers that may contain duplicates, return all the distinct permutations.
nums = [1,1,2] output = [[1,1,2],[1,2,1],[2,1,1]]
Why the solution works
Fill the permutation one position at a time. For the current position try each value that is still available, recurse to fill the rest, then undo the choice and try the next value. The recursion visits every permutation exactly once.
Treating the two 1s as different elements would produce every answer twice. Keeping a count per distinct value and trying each value once per position removes the duplicates at the source.
The “undo” line is the heart of backtracking: after the recursive call returns, the state must be exactly what it was before the choice.
Complexity: O(n · n!) time in the worst case, O(n) memory besides the output.
Watch out
- Every change made before the recursive call must be undone after it.
- A missing or wrong base case means infinite recursion.
- Treating equal items as different produces duplicates: loop over distinct values, as the counts do here.