Backtracking Patterns

Master Backtracking Patterns for DSA + Competitive Programming

Backtracking explores all valid configurations by building a solution incrementally and abandoning paths that violate constraints.

“Try → Explore → Undo” — the three-step dance of constraint satisfaction.

---

Pattern Table

Pattern	Typical Questions	Keywords / Detection Cues
Constraint Satisfaction	N-Queens, Sudoku	valid, constraint, arrangement
Grid Backtracking	Word Search, Rat in Maze	grid, direction, path found
Pruning & Optimization	Permutations with duplicates	prune, branch & bound, skip duplicates
Subset / Combination Generation	Subsets II, combination sum	duplicates, skip, sort

---

Mental Trigger

Invalid? Prune. Complete? Record. Otherwise → Try each choice → Recurse → Undo.

---

Generic Java Backtracking Template (Base)

public void backtrack(State state) {
    if (isInvalid(state)) return;
    if (isComplete(state)) {
        saveSolution(state);
        return;
    }

    for (Choice choice : getChoices(state)) {
        makeChoice(state, choice);
        backtrack(state);
        undoChoice(state, choice);      // backtrack step
    }
}

Everything in Backtracking is try → explore → undo with constraints.

---

Recognition Cheat Sheet

If you see…	Think…
All valid configurations	Constraint satisfaction
Grid + path exists	Grid backtracking
Find all with constraints	Backtracking + pruning
Skip invalid early	Pruning