Backtracking Core Idea Backtracking is controlled brute force: dfs(state): if state is complete: record answer return for choice in valid choices from state: choose dfs(next state) undo Common Shapes Pick Or Skip Use when every element has exactly two choices: take it or leave it.
Forward index Use this when recursion moves forward through an array or string.
Over a state Use this when recursion places something into a row, cell, grid path, bucket, or slot while constraints decide whether the choice is legal.
Permutations And Counts Use this when order matters. The recursion fills one position at a time by choosing from values that remain available.
Trick is often “verification” being easier vs finding the value. Monotonicity of course is needed ^ on the answer space.
K-th Order Find K-th Smallest Pair Distance Whenever you think of log squared → a sliding window is almost always possible.
Split Array Largest Sum ( greedy split ).
Specials Median of Two Sorted Arrays Two ways: k/2 elimination, or binary search the cut size in the smaller array until the boundary condition holds.
Interval DP Core: optimal solution for [i, j] is f(some continuous split of the interval).
Interval DP Problems Shared Boundary (Points / Coordinates) 1547. Minimum Cost to Cut a Stick 312. Burst Balloons 1039.