Exhaustive recursion introduction

Exhaustive recursion (backtracking)

Sometimes you don't want the answer — you want all of them: every subset, every permutation, every way to fill a knapsack. Exhaustive recursion (a.k.a. backtracking) systematically explores every possibility by making a choice, recursing, then undoing the choice to try the next one.

The decision-tree mindset

At each step you face a choice. Each choice branches the search:

Include or exclude this element? → generates subsets.
Which unused element goes next? → generates permutations.
Which option for this slot? → generates all combinations of options.

Following every branch to the leaves enumerates the entire space.

The template

function explore(choicesSoFar, remaining):
    if nothingLeftToDecide:
        record(choicesSoFar)
        return
    for each option in optionsFor(remaining):
        choose(option)
        explore(updatedChoices, smallerRemaining)
        unchoose(option)        // backtrack

The "unchoose" step (backtrack) restores state so the next branch starts clean. With immutable copies you can skip explicit undo — just pass new slices down.

The cost

Exhaustive search is inherently expensive: there are 2ⁿ subsets and n! permutations, so these algorithms are exponential or factorial. That's unavoidable when the output itself is that large. Backtracking's value is pruning — abandoning a branch as soon as it can't lead to a valid answer, so you skip whole regions of the tree.

The problems here drill the classic shapes: subsets, permutations, combinations, and choice-expansion. Learn to see the decision tree and the code writes itself.