Algorithm Design Paradigms

Backtracking

Explore a solution space depth-first, building a partial solution incrementally and abandoning ("backtracking" from) any branch that can't possibly succeed. It is brute-force search made tractable by pruning early.

The shape: choose a candidate for the next slot, recurse, undo the choice on return — the "undo" step is what distinguishes backtracking from plain recursive enumeration
Pruning ("is this partial solution still viable?") is what separates a backtracking algorithm that finishes in milliseconds from one that never terminates
Classic applications: N-Queens, Sudoku, generating permutations/subsets/combinations, graph coloring, constraint satisfaction
Worst-case complexity is exponential — backtracking makes an exponential problem practical, not polynomial
Distinct from plain recursion in that state is mutated in place and explicitly reverted, which keeps memory usage to the recursion depth instead of copying state at every call

N-Queens — choose, recurse, undo

boolean[] cols = new boolean[n], diag1 = new boolean[2 * n], diag2 = new boolean[2 * n];

boolean solve(int row, int n, int[] placement) {
    if (row == n) return true;                    // base case: all rows placed

    for (int col = 0; col < n; col++) {
        if (cols[col] || diag1[row + col] || diag2[row - col + n]) continue;  // prune

        placement[row] = col;                       // choose
        cols[col] = diag1[row + col] = diag2[row - col + n] = true;

        if (solve(row + 1, n, placement)) return true;   // recurse

        cols[col] = diag1[row + col] = diag2[row - col + n] = false;         // undo
    }
    return false;   // every column in this row failed — backtrack further up
}

The three booleans arrays turn "is this square attacked" from an O(n) scan into O(1) — pruning speed matters as much as the pruning logic itself