Backtracking

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   DFS over a tree of partial answers: choose a piece, explore the rest, un-choose it. The undo lets one shared path serve every branch.

   #1
2. ↯use it when

   "Return all …" (subsets, orders, partitions, boards) or "place under rules", with small n: about 20 for 2ⁿ, about 10 for n!.

   #2
3. { }template

   if (goal) { record a copy; return; } then for (choice) { choose; backtrack(next); un-choose; }

   #3
4. O( )cost

   Nodes × work per node. Subsets O(n·2ⁿ) · permutations O(n·n!) · k of n O(k·C(n, k)). Extra space = depth, O(n).

   #4
5. !trap

   result.add(path) stores a reference that ends up empty. Always result.add(new ArrayList<>(path)).

   #5
6. !trap

   Duplicates: sort, then if (i > start && a[i] == a[i - 1]) continue;. With i > 0 you lose answers like [1, 2, 2].

   #6
7. ✦pro tip

   Order ignored → loop from start. Order matters → loop from 0 with used[]. Reuse allowed → recurse with i, not i + 1.

   #7
8. ✦pro tip

   Prune before the call: sort + break, a loop bound, O(1) attack tables. Need one answer? Return boolean and stop on true.

   #8
9. ↯use it when

   Asked to count or find a min/max, with n in the hundreds or more? That's DP, not backtracking.

   #9

Shaky on a card? Open the chapter or flip its recall cards.