DSA · interactive
Backtracking: subsets that sum to 3
Find every subset of [3, 1, 2] that adds up to 3. At each number, try taking it, then try skipping it, then undo and go back. Pruning stops exploring a branch as soon as it can't work.
level 1: take or skip 3level 2: take or skip 1level 3: take or skip 2
030431064533120
Numbers are running sums. Solid line: take. Dashed: skip. Red ring: pruned.
path {} · visited 1/15 · found —
Start empty. At each level, decide: take this number or skip it.
Pruning
1 2 3 4 All numbers are positive, so once the sum reaches the target, going deeper can't help. Pruning is what makes backtracking usable.
Same pattern: permutations, N-Queens, Sudoku.
Now solve it
Backtracking: 10 problems
See all →In production
Tools and technologies
Backtracking is the core of constraint solvers.
Not tied to one language — use these names when you search docs or design a system.