Backtracking

O(2^n)/O(n!)

Recursion that builds a candidate one choice at a time, explores deeper, and undoes the last choice on the way back to try the next one, enumerating every valid arrangement.

Signals

generate all subsets/permutations/combinationsn is small (roughly n <= 12-20), exponential search is acceptablemake a choice, recurse, then undo it before trying the next choiceplace items under constraints and back off on conflict (N-Queens, Sudoku)return every valid arrangement, not just one

Template

function backtrack(path, choices, result) {
    if (path.length === choices.length) { // or another stop condition
        result.push([...path]);
        return;
    }
    for (const choice of choices) {
        path.push(choice); // choose
        backtrack(path, choices, result); // explore
        path.pop(); // undo
    }
}

Looks similar, isn't

Plain recursion: Plain recursion visits tree-shaped data and returns a value. Backtracking adds the choose/explore/undo loop needed to enumerate every subset, permutation, or placement rather than compute a single answer.
Dynamic programming: DP reuses overlapping subproblems to avoid recomputation and returns one optimal value. Backtracking enumerates every distinct arrangement, so there is no shared subproblem to cache.

n small (n <= 12-20, the search space is exponential) -> O(2^n) for subsets or O(n!) for permutations, each branch doing O(1)-O(n) work to build and undo a choice.

Learn this pattern