Recursion, backtracking, and dynamic programming.

Backtracking traverses a decision tree and restores mutable state before trying the next edge. Dynamic programming collapses repeated decision subtrees by assigning each distinct state one answer. The hard part is not the table. It is defining a state that contains exactly the information needed by future choices.

Backtracking: choose, recurse, undo

The path represents decisions made from the root to the current node. A recursive call explores every completion of that prefix. Undoing the choice restores the exact state observed at loop entry so the next choice starts from the same parent.

permutations.cppstd::vector<std::vector<int>> permutations(
    std::span<const int> values
) {
    std::vector<std::vector<int>> answer;
    std::vector<int> path;
    std::vector<bool> used(values.size(), false);

    const auto search = [&](const auto& self) -> void {
        if (path.size() == values.size()) {
            answer.push_back(path); // copy the completed path
            return;
        }
        for (std::size_t i = 0; i < values.size(); ++i) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(values[i]);
            self(self);
            path.pop_back();
            used[i] = false;
        }
    };
    search(search);
    return answer;
}

Subsets use a start index rather than a used array because each recursive call may choose only later elements. Combination Sum passes the same index again when reuse is allowed and the next index when each candidate is single-use. Word Search mutates the board to mark the current path, then restores the character before returning.

subsets.cppstd::vector<std::vector<int>> subsets(
    std::span<const int> values
) {
    std::vector<std::vector<int>> answer;
    std::vector<int> path;

    const auto search = [&](const auto& self, std::size_t next) -> void {
        answer.push_back(path);
        for (std::size_t i = next; i < values.size(); ++i) {
            path.push_back(values[i]);
            self(self, i + 1);
            path.pop_back();
        }
    };
    search(search, 0);
    return answer;
}

Duplicate choices and pruning

Sort values before skipping duplicate choices. In a combinations-style loop, skip values[i] == values[i - 1] only when both are candidates at the same recursion depth:

skip_duplicate_choices.cppfor (std::size_t i = next; i < values.size(); ++i) {
    if (i > next && values[i] == values[i - 1]) continue;
    path.push_back(values[i]);
    search(i + 1);
    path.pop_back();
}

In unique permutations, the condition changes: skip an equal value when the previous equal index has not been used on the current path. This forces equal values to enter in a consistent order:

unique_permutation_guard.cppif (used[i]) continue;
if (i > 0 && values[i] == values[i - 1] && !used[i - 1]) continue;

Prune only with a valid bound. If candidates are positive and sorted, Combination Sum can stop the loop when the next value exceeds the remainder. That pruning is invalid if negative values are permitted. N-Queens stores occupied columns and diagonals so a partial board is rejected in constant time instead of rescanning the board.

Dynamic-programming workflow

1. Define the state in a sentence. Example: best[i] is the maximum amount obtainable from the first i houses.
2. Write the choices and transition. Skip house i, or take it and combine with the answer two positions back.
3. Set base states. State zero is not an afterthought. It lets transitions handle the first real item uniformly.
4. Memoize the recursive form. This confirms that the state is sufficient and exposes how many distinct states exist.
5. Choose an evaluation order. Every dependency must be computed before the state that reads it.
6. Compress memory only after correctness. Retain exactly the dependency frontier, not blindly one row.

Linear DP

House Robber has two choices at each house: skip it and retain the previous best, or take it and add its value to the best ending two positions earlier. The table depends on only two earlier values, so two scalars are sufficient.

house_robber.cppint house_robber(std::span<const int> values) {
    int two_back = 0;
    int one_back = 0;
    for (const int value : values) {
        const int current = std::max(one_back, two_back + value);
        two_back = one_back;
        one_back = current;
    }
    return one_back;
}

Maximum Subarray is linear DP where the state is the best sum ending exactly at the current index. Decode Ways depends on one- and two-digit suffixes but requires validity checks for zero. House Robber II breaks the cycle into two linear cases: exclude the first house or exclude the last.

0/1 and unbounded knapsack

Coin Change is unbounded: after using a coin, the same coin remains available. best[amount] is the fewest coins needed for that exact amount. Initialize unreachable states above every possible answer rather than to zero.

coin_change.cppint coin_change(std::span<const int> coins, int amount) {
    const int unreachable = amount + 1;
    std::vector<int> best(
        static_cast<std::size_t>(amount + 1),
        unreachable
    );
    best[0] = 0;

    for (int total = 1; total <= amount; ++total)
        for (const int coin : coins)
            if (coin <= total)
                best[static_cast<std::size_t>(total)] = std::min(
                    best[static_cast<std::size_t>(total)],
                    best[static_cast<std::size_t>(total - coin)] + 1
                );
    const int answer = best[static_cast<std::size_t>(amount)];
    return answer == unreachable ? -1 : answer;
}

One-dimensional 0/1 knapsack iterates capacity downward. Descending order ensures the current item cannot read a state already updated by that same item. Unbounded knapsack iterates upward when reuse in the same item pass is intended.

partition_equal.cppbool can_partition_equal(std::span<const int> values) {
    const int total = std::accumulate(values.begin(), values.end(), 0);
    if (total % 2 != 0) return false;
    const int target = total / 2;
    std::vector<bool> reachable(
        static_cast<std::size_t>(target + 1),
        false
    );
    reachable[0] = true;

    for (const int value : values)
        for (int sum = target; sum >= value; --sum)
            reachable[static_cast<std::size_t>(sum)] =
                reachable[static_cast<std::size_t>(sum)] ||
                reachable[static_cast<std::size_t>(sum - value)];
    return reachable[static_cast<std::size_t>(target)];
}

Two-sequence grids

For LCS, state (i, j) describes the two prefixes ending before indices i and j. Matching characters extend the diagonal state. A mismatch discards one final character from either prefix. Only the previous and current rows are needed.

longest_common_subsequence.cppint longest_common_subsequence(
    std::string_view left,
    std::string_view right
) {
    std::vector<int> previous(right.size() + 1, 0);
    std::vector<int> current(right.size() + 1, 0);

    for (const char left_character : left) {
        for (std::size_t column = 1; column <= right.size(); ++column) {
            if (left_character == right[column - 1])
                current[column] = previous[column - 1] + 1;
            else
                current[column] =
                    std::max(previous[column], current[column - 1]);
        }
        std::swap(previous, current);
        std::fill(current.begin(), current.end(), 0);
    }
    return previous.back();
}

Edit Distance uses the same grid but minimizes delete, insert, and replace transitions. Distinct Subsequences counts ways and therefore adds transitions. Longest Palindromic Subsequence is LCS between the string and its reverse, although direct interval DP avoids materializing a second string.

Increasing subsequence state

The direct DP defines length[i] as the best increasing subsequence ending at i and scans every earlier smaller value, producing O(n²). The optimized method stores tails[len], the smallest possible final value of an increasing subsequence of length len + 1. A smaller tail leaves more room for future extension.

lis_tails.cppint lis_length(std::span<const int> values) {
    std::vector<int> tails;
    for (const int value : values) {
        const auto position =
            std::lower_bound(tails.begin(), tails.end(), value);
        if (position == tails.end()) tails.push_back(value);
        else *position = value;
    }
    return static_cast<int>(tails.size());
}

tails is not itself an LIS. Reconstructing one needs parent indices and the source index that currently supplies each length. Nondecreasing subsequences use upper_bound. Bounded value differences or range-dependent transitions require a segment tree over compressed values, covered in the next chapter.

Interval DP

Burst Balloons is difficult if the state chooses the first balloon: its neighbors depend on later choices. Choose the last balloon inside (left, right). At that moment, the boundaries are still present, and the two interior intervals have already been solved.

burst_balloons.cppint burst_balloons(std::span<const int> values) {
    std::vector<int> padded{1};
    padded.insert(padded.end(), values.begin(), values.end());
    padded.push_back(1);
    const std::size_t n = padded.size();
    std::vector best(n, std::vector<int>(n, 0));

    for (std::size_t width = 2; width < n; ++width)
        for (std::size_t left = 0; left + width < n; ++left) {
            const std::size_t right = left + width;
            for (std::size_t last = left + 1; last < right; ++last)
                best[left][right] = std::max(
                    best[left][right],
                    best[left][last] + best[last][right] +
                        padded[left] * padded[last] * padded[right]
                );
        }
    return best[0][n - 1];
}

Bitmask DP

Encode a subset in an integer. Bit i is one when item i is present. mask | (1 << i) adds an item, mask & (mask - 1) removes the lowest set bit, and std::popcount gives the number of chosen items.

assignment_dp.cpplong long minimum_assignment_cost(
    const std::vector<std::vector<int>>& cost
) {
    const std::size_t n = cost.size();
    const std::size_t states = std::size_t{1} << n;
    const long long inf = std::numeric_limits<long long>::max() / 4;
    std::vector<long long> best(states, inf);
    best[0] = 0;

    for (std::size_t mask = 0; mask < states; ++mask) {
        const std::size_t worker = std::popcount(mask);
        if (worker == n) continue;
        for (std::size_t job = 0; job < n; ++job) {
            if ((mask & (std::size_t{1} << job)) != 0) continue;
            const std::size_t next = mask | (std::size_t{1} << job);
            best[next] = std::min(
                best[next],
                best[mask] + cost[worker][job]
            );
        }
    }
    return best.back();
}

This is O(n 2ⁿ), which is excellent for n=18 and impossible for n=50. Traveling Salesperson adds the current endpoint to the subset state. Enumerating every submask of a mask uses for (sub = mask; sub; sub = (sub - 1) & mask) and costs O(3ⁿ) across all masks.