Almost every backtracking question fits one of two templates, and the difference is the shape of the decision tree — what you choose at each level. Add pruning — refusing to explore a branch that can't work — and the same template solves puzzles that would otherwise take forever.
Walk the items in order. At each item there are exactly two choices: take it or skip it. The tree is binary and n levels deep, with 2ⁿ leaves — one per subset. Subsets, Target Sum and many "pick some items" problems look like this.
solve(i):
if i == n: record the path; return
path.add(items[i]); solve(i + 1); path.remove() # take items[i]
solve(i + 1) # skip items[i]At each level, loop over every option still allowed and try each in turn. The tree can have many branches per node. Two common rules decide what's allowed:
start index and only choose items at or after it, so {1, 2} is never built again as {2, 1}.used array.solve(start):
if the path is complete: record a copy; return
for each choice c allowed from start:
if c breaks a rule: continue # prune
path.add(c); solve(next); path.remove()Most backtracking problems have rules. Checking a rule only at the leaves wastes the whole subtree; checking it as soon as a choice is made cuts the branch off before any of its descendants are built. The example: binary strings of length n with no two 1s next to each other. A 1 right after a 1 can never be fixed later, so don't explore it at all.
Each branch that would put a 1 after a 1 is cut before it's explored.
function noAdjacentOnes(n) { const result = []; const path = []; const build = () => { if (path.length === n) { result.push(path.join("")); return; } path.push("0"); // a 0 is always allowed build(); path.pop(); if (path[path.length - 1] !== "1") { // prune: a 1 right after a 1 can never work path.push("1"); build(); path.pop(); } }; build(); return result;}The answers grow like the Fibonacci numbers (about 1.6ⁿ) instead of 2ⁿ, and the search does work only for strings that can still succeed. On harder puzzles — N-Queens, Sudoku — pruning is the difference between milliseconds and years.
problem leaves (answers) time
subsets of n 2^n O(2^n · n)
combinations, k of n C(n, k) O(C(n, k) · k)
permutations of n n! O(n! · n)
k choices at each of n steps k^n O(k^n · n)
space: O(n) for the path and the call stack, plus the outputThe extra factor n is for copying each answer. Pruning can't change these worst cases, but in practice it often cuts the tree down enormously.
start) or permutations (with used).