Bitmask DP and Sum-Over-Subsets (SOS) DP

1. Introduction: State as a Bitmask

Many combinatorial problems have a natural brute-force solution that tries every ordering, every subset, or every assignment of a small collection of elements. When the number of elements $n$ is small — roughly $n \le 20$ — a different technique becomes available: encode which subset of elements has already been used, visited, or assigned as a single integer, and let dynamic programming operate directly over that integer.

This is bitmask DP. Instead of a DP state built from an index or a length, the state includes a mask $\in [0, 2^n)$ whose bit $i$ records whether element $i$ has been consumed. Because there are only $2^n$ possible masks, an exponential search over orderings (which can be $n!$ possibilities) collapses into a polynomial-in-$2^n$ table of subproblems, each solved once and reused.

The same bitmask-as-state idea also powers a second, related technique covered later in this lesson: Sum-Over-Subsets (SOS) DP, which computes, for every mask simultaneously, an aggregate over all of that mask's submasks — in $O(n \cdot 2^n)$ instead of the $O(3^n)$ that naive per-mask submask enumeration would cost.

2. Prerequisites

This lesson assumes comfort with two things this site already covers in depth:

• Basic bitmask mechanics: representing a subset of $n$ elements as an $n$-bit integer and enumerating all $2^n$ subsets by counting a mask from 0 to (1<<n)-1. This mechanic is covered in the Bitmasks for Subsets section of the Bit Manipulation lesson and is not re-derived here — if for mask in range(1<<n) and (mask >> i) & 1 are unfamiliar, read that section first.
• General DP methodology: identifying overlapping subproblems, defining state precisely, deriving a recurrence, and choosing memoization versus tabulation, as built up in Dynamic Programming Foundations. Bitmask DP is not a separate discipline from that methodology — it is ordinary DP where the state happens to be a bitmask instead of an index.

3. A Concrete Example: TSP by Hand

Notice what made this tractable: instead of trying all $3! = 6$ orderings of the non-start cities individually (which would not scale), the DP shares work across orderings that visit the same set of cities and end at the same city — regardless of the order those cities were visited in. That sharing is exactly what the bitmask state buys.

4. Subset States: Traveling Salesman Problem

Processing masks in increasing numeric order guarantees correctness without recursion: every transition goes from mask to mask | (1<<next), which is numerically larger, so by the time a mask is read as a source it has already received every update from its predecessors.

import math

def tsp_min_cost(cost):
    n = len(cost)
    full = 1 << n
    INF = math.inf
    dp = [[INF] * n for _ in range(full)]
    dp[1][0] = 0  # only city 0 visited, path currently at city 0

    for mask in range(full):
        for last in range(n):
            if dp[mask][last] == INF or not (mask & (1 << last)):
                continue
            for nxt in range(n):
                if mask & (1 << nxt):
                    continue  # nxt already visited
                new_mask = mask | (1 << nxt)
                new_cost = dp[mask][last] + cost[last][nxt]
                if new_cost < dp[new_mask][nxt]:
                    dp[new_mask][nxt] = new_cost

    full_mask = full - 1
    return min(dp[full_mask][last] + cost[last][0] for last in range(1, n))

cost = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
]
print("Minimum tour cost:", tsp_min_cost(cost))  # Minimum tour cost: 80

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

int tspMinCost(const std::vector<std::vector<int>>& cost) {
    int n = cost.size();
    int full = 1 << n;
    const int INF = INT_MAX / 2;
    std::vector<std::vector<int>> dp(full, std::vector<int>(n, INF));
    dp[1][0] = 0;

    for (int mask = 0; mask < full; ++mask) {
        for (int last = 0; last < n; ++last) {
            if (dp[mask][last] == INF || !(mask & (1 << last))) continue;
            for (int nxt = 0; nxt < n; ++nxt) {
                if (mask & (1 << nxt)) continue;
                int newMask = mask | (1 << nxt);
                int newCost = dp[mask][last] + cost[last][nxt];
                if (newCost < dp[newMask][nxt]) {
                    dp[newMask][nxt] = newCost;
                }
            }
        }
    }

    int fullMask = full - 1;
    int best = INF;
    for (int last = 1; last < n; ++last) {
        best = std::min(best, dp[fullMask][last] + cost[last][0]);
    }
    return best;
}

int main() {
    std::vector<std::vector<int>> cost = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    std::cout << "Minimum tour cost: " << tspMinCost(cost) << '\n'; // Minimum tour cost: 80
}

import java.util.Arrays;

public class TSPBitmaskDP {
    static int tspMinCost(int[][] cost) {
        int n = cost.length;
        int full = 1 << n;
        final int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[full][n];
        for (int[] row : dp) Arrays.fill(row, INF);
        dp[1][0] = 0;

        for (int mask = 0; mask < full; mask++) {
            for (int last = 0; last < n; last++) {
                if (dp[mask][last] == INF || (mask & (1 << last)) == 0) continue;
                for (int next = 0; next < n; next++) {
                    if ((mask & (1 << next)) != 0) continue;
                    int newMask = mask | (1 << next);
                    int newCost = dp[mask][last] + cost[last][next];
                    if (newCost < dp[newMask][next]) {
                        dp[newMask][next] = newCost;
                    }
                }
            }
        }

        int fullMask = full - 1;
        int best = INF;
        for (int last = 1; last < n; last++) {
            best = Math.min(best, dp[fullMask][last] + cost[last][0]);
        }
        return best;
    }

    public static void main(String[] args) {
        int[][] cost = {
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };
        System.out.println("Minimum tour cost: " + tspMinCost(cost)); // Minimum tour cost: 80
    }
}

All three panels implement the same recurrence verified by hand above and print 80. The DP has $2^n \cdot n$ states, each with an $O(n)$ transition, so it explores the search space that would otherwise require $O(n!)$ orderings in $O(2^n \cdot n^2)$ time.

5. Assignment DP and Set Partition DP

This is a strictly smaller state than the TSP DP above — dp[mask] instead of dp[mask][last] — because the "current position" (which worker is being assigned) is a deterministic function of the mask rather than independent information that must be tracked alongside it.

import math

def assignment_min_cost(cost):
    n = len(cost)
    full = 1 << n
    dp = [math.inf] * full
    dp[0] = 0

    for mask in range(full):
        if dp[mask] == math.inf:
            continue
        worker = bin(mask).count("1")  # next worker to assign a task
        if worker == n:
            continue
        for task in range(n):
            if mask & (1 << task):
                continue  # task already assigned
            new_mask = mask | (1 << task)
            new_cost = dp[mask] + cost[worker][task]
            if new_cost < dp[new_mask]:
                dp[new_mask] = new_cost

    return dp[full - 1]

cost = [
    [9, 2, 7],
    [6, 4, 3],
    [5, 8, 1],
]
print("Minimum assignment cost:", assignment_min_cost(cost))  # Minimum assignment cost: 9

#include <iostream>
#include <vector>
#include <climits>

int assignmentMinCost(const std::vector<std::vector<int>>& cost) {
    int n = cost.size();
    int full = 1 << n;
    const int INF = INT_MAX / 2;
    std::vector<int> dp(full, INF);
    dp[0] = 0;

    for (int mask = 0; mask < full; ++mask) {
        if (dp[mask] == INF) continue;
        int worker = __builtin_popcount(mask);
        if (worker == n) continue;
        for (int task = 0; task < n; ++task) {
            if (mask & (1 << task)) continue;
            int newMask = mask | (1 << task);
            int newCost = dp[mask] + cost[worker][task];
            if (newCost < dp[newMask]) {
                dp[newMask] = newCost;
            }
        }
    }

    return dp[full - 1];
}

int main() {
    std::vector<std::vector<int>> cost = {
        {9, 2, 7},
        {6, 4, 3},
        {5, 8, 1}
    };
    std::cout << "Minimum assignment cost: " << assignmentMinCost(cost) << '\n'; // Minimum assignment cost: 9
}

import java.util.Arrays;

public class AssignmentBitmaskDP {
    static int assignmentMinCost(int[][] cost) {
        int n = cost.length;
        int full = 1 << n;
        final int INF = Integer.MAX_VALUE / 2;
        int[] dp = new int[full];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int mask = 0; mask < full; mask++) {
            if (dp[mask] == INF) continue;
            int worker = Integer.bitCount(mask);
            if (worker == n) continue;
            for (int task = 0; task < n; task++) {
                if ((mask & (1 << task)) != 0) continue;
                int newMask = mask | (1 << task);
                int newCost = dp[mask] + cost[worker][task];
                if (newCost < dp[newMask]) {
                    dp[newMask] = newCost;
                }
            }
        }

        return dp[full - 1];
    }

    public static void main(String[] args) {
        int[][] cost = {
            {9, 2, 7},
            {6, 4, 3},
            {5, 8, 1}
        };
        System.out.println("Minimum assignment cost: " + assignmentMinCost(cost)); // Minimum assignment cost: 9
    }
}

Checking by brute force: of the $3! = 6$ ways to assign 3 tasks to 3 workers, worker0→task1 (2), worker1→task0 (6), worker2→task2 (1) totals 9, and no other permutation does better. The DP explores $O(2^n)$ masks with $O(n)$ transitions each, so it finds this minimum in $O(n \cdot 2^n)$ instead of $O(n!)$.

Set Partition DP

A related state, dp[mask] = the minimum number of valid subsets needed to partition exactly the elements in mask, where "valid" means some condition holds for a subset (here, its sum does not exceed a limit). Instead of trying one next element, the recurrence tries every valid first subset as a submask of mask: dp[mask] = min over valid submask sub of mask of dp[mask ^ sub] + 1, with dp[0] = 0. This uses the submask-enumeration trick from the next section applied inside a DP transition, rather than to a standalone aggregate.

def min_partitions(values, limit):
    n = len(values)
    full = 1 << n

    # subset_sum[mask] = sum of values at the set bits of mask
    subset_sum = [0] * full
    for mask in range(1, full):
        low_bit = mask & (-mask)
        idx = low_bit.bit_length() - 1
        subset_sum[mask] = subset_sum[mask ^ low_bit] + values[idx]

    INF = float("inf")
    dp = [INF] * full
    dp[0] = 0

    for mask in range(1, full):
        sub = mask
        while sub > 0:
            if subset_sum[sub] <= limit and dp[mask ^ sub] + 1 < dp[mask]:
                dp[mask] = dp[mask ^ sub] + 1
            sub = (sub - 1) & mask

    return dp[full - 1]

values = [4, 5, 6, 3]
print("Minimum partitions:", min_partitions(values, 9))  # Minimum partitions: 2

#include <iostream>
#include <vector>
#include <climits>

int minPartitions(const std::vector<int>& values, int limit) {
    int n = values.size();
    int full = 1 << n;
    std::vector<int> subsetSum(full, 0);
    for (int mask = 1; mask < full; ++mask) {
        int lowBit = mask & (-mask);
        int idx = __builtin_ctz(lowBit);
        subsetSum[mask] = subsetSum[mask ^ lowBit] + values[idx];
    }

    const int INF = INT_MAX / 2;
    std::vector<int> dp(full, INF);
    dp[0] = 0;

    for (int mask = 1; mask < full; ++mask) {
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            if (subsetSum[sub] <= limit && dp[mask ^ sub] + 1 < dp[mask]) {
                dp[mask] = dp[mask ^ sub] + 1;
            }
        }
    }

    return dp[full - 1];
}

int main() {
    std::vector<int> values = {4, 5, 6, 3};
    std::cout << "Minimum partitions: " << minPartitions(values, 9) << '\n'; // Minimum partitions: 2
}

import java.util.Arrays;

public class SetPartitionBitmaskDP {
    static int minPartitions(int[] values, int limit) {
        int n = values.length;
        int full = 1 << n;
        int[] subsetSum = new int[full];
        for (int mask = 1; mask < full; mask++) {
            int lowBit = mask & (-mask);
            int idx = Integer.numberOfTrailingZeros(lowBit);
            subsetSum[mask] = subsetSum[mask ^ lowBit] + values[idx];
        }

        final int INF = Integer.MAX_VALUE / 2;
        int[] dp = new int[full];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int mask = 1; mask < full; mask++) {
            for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
                if (subsetSum[sub] <= limit && dp[mask ^ sub] + 1 < dp[mask]) {
                    dp[mask] = dp[mask ^ sub] + 1;
                }
            }
        }

        return dp[full - 1];
    }

    public static void main(String[] args) {
        int[] values = {4, 5, 6, 3};
        System.out.println("Minimum partitions: " + minPartitions(values, 9)); // Minimum partitions: 2
    }
}

With values = [4, 5, 6, 3] and limit = 9, the total sum is 18, so a single subset cannot hold everything. But {4, 5} and {6, 3} each sum to exactly 9, so two partitions suffice — matching the printed result.

6. Submask Enumeration

Run this loop for every mask from 0 to (1<<n)-1 and the total number of (mask, submask) iterations across the whole outer loop is $O(3^n)$ — not the $O(4^n)$ a first, incorrect mental model might suggest from "for each of $2^n$ masks, for each of $2^n$ possible submasks."

Why $3^n$: fix one pair (mask, submask) with submask ⊆ mask, and look at bit position $i$ independently across all $n$ positions. Bit $i$ can be in exactly one of three states relative to that pair: absent from mask (and therefore absent from sub); present in mask but absent from sub; or present in both. Three independent choices per bit, across $n$ bits, gives $3^n$ total (mask, submask) pairs when the empty submask is included — and $3^n - 2^n$ when the loop skips it, since every one of the $2^n$ masks loses exactly its one empty-submask pairing. Both quantities are $\Theta(3^n)$.

def enumerate_submasks(mask):
    """Every nonzero submask of mask, from mask itself down to its lowest bit."""
    submasks = []
    sub = mask
    while sub > 0:
        submasks.append(sub)
        sub = (sub - 1) & mask
    return submasks

# n = 3, mask = 0b101 (bits 0 and 2 set)
mask = 0b101
print("Nonzero submasks of 0b101:", [bin(s) for s in enumerate_submasks(mask)])
# Nonzero submasks of 0b101: ['0b101', '0b100', '0b1']

# Verify the O(3^n) claim directly for n = 3
n = 3
nonzero_pairs = sum(len(enumerate_submasks(m)) for m in range(1 << n))
print("Nonzero (mask, submask) pairs, n=3:", nonzero_pairs)                 # 19
print("Including the empty submask (3**n):", 3 ** n)                       # 27
print("Difference = one empty submask per mask (2**n):", 3 ** n - nonzero_pairs)  # 8

#include <iostream>
#include <vector>
#include <bitset>

std::vector<int> enumerateSubmasks(int mask) {
    std::vector<int> submasks;
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
        submasks.push_back(sub);
    }
    return submasks;
}

int main() {
    int mask = 0b101; // bits 0 and 2 set
    std::cout << "Nonzero submasks of 0b101:";
    for (int s : enumerateSubmasks(mask)) {
        std::cout << " " << std::bitset<3>(s);
    }
    std::cout << '\n'; // Nonzero submasks of 0b101: 101 100 001

    int n = 3;
    long long nonzeroPairs = 0;
    for (int m = 0; m < (1 << n); ++m) {
        nonzeroPairs += enumerateSubmasks(m).size();
    }
    long long total = 1;
    for (int i = 0; i < n; ++i) total *= 3;

    std::cout << "Nonzero (mask, submask) pairs, n=3: " << nonzeroPairs << '\n';           // 19
    std::cout << "Including the empty submask (3^n): " << total << '\n';                    // 27
    std::cout << "Difference = one empty submask per mask (2^n): " << (total - nonzeroPairs) << '\n'; // 8
}

import java.util.ArrayList;
import java.util.List;

public class SubmaskEnumeration {
    static List<Integer> enumerateSubmasks(int mask) {
        List<Integer> submasks = new ArrayList<>();
        for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
            submasks.add(sub);
        }
        return submasks;
    }

    public static void main(String[] args) {
        int mask = 0b101; // bits 0 and 2 set
        System.out.print("Nonzero submasks of 0b101:");
        for (int s : enumerateSubmasks(mask)) {
            System.out.print(" " + Integer.toBinaryString(s));
        }
        System.out.println(); // Nonzero submasks of 0b101: 101 100 1

        int n = 3;
        long nonzeroPairs = 0;
        for (int m = 0; m < (1 << n); m++) {
            nonzeroPairs += enumerateSubmasks(m).size();
        }
        long total = (long) Math.pow(3, n);

        System.out.println("Nonzero (mask, submask) pairs, n=3: " + nonzeroPairs);                       // 19
        System.out.println("Including the empty submask (3^n): " + total);                                // 27
        System.out.println("Difference = one empty submask per mask (2^n): " + (total - nonzeroPairs));  // 8
    }
}

7. Sum Over Subsets (SOS) DP

Think of a conceptual layer dp[i][mask] = the sum of f[sub] over every submask sub of mask that agrees with mask on every bit above position $i$ — that is, only bits $0..i$ are allowed to differ between sub and mask. At layer $i=-1$, no bit is allowed to differ, so dp[-1][mask] = f[mask]. Moving from layer $i-1$ to layer $i$ additionally allows bit $i$ to be cleared: if bit $i$ of mask is set, the newly-allowed submasks are exactly the old ones with bit $i$ cleared, so dp[i][mask] = dp[i-1][mask] + dp[i-1][mask \oplus (1<<i)]; if bit $i$ of mask is already 0, nothing new becomes allowed and dp[i][mask] = dp[i-1][mask]. After all $n$ layers, dp[n-1][mask] = g[mask].

Because layer $i$ only ever reads layer $i-1$ at the same mask and at mask with bit $i$ cleared — and both of those already hold their final layer-$(i-1)$ value before layer $i$ begins — the layer dimension can be dropped and the update done in place, one bit at a time, over a single array:

def sos_dp(f, n):
    """g[mask] = sum of f[sub] for every submask sub of mask, for all 2**n masks."""
    g = f[:]
    for i in range(n):
        for mask in range(1 << n):
            if mask & (1 << i):
                g[mask] += g[mask ^ (1 << i)]
    return g

n = 3
f = [1, 2, 3, 4, 5, 6, 7, 8]  # f[mask] for every 3-bit mask, 0..7
g = sos_dp(f, n)
print("g:", g)  # g: [1, 3, 4, 10, 6, 14, 16, 36]

#include <iostream>
#include <vector>

std::vector<long long> sosDP(std::vector<long long> f, int n) {
    std::vector<long long> g = f;
    for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (mask & (1 << i)) {
                g[mask] += g[mask ^ (1 << i)];
            }
        }
    }
    return g;
}

int main() {
    int n = 3;
    std::vector<long long> f = {1, 2, 3, 4, 5, 6, 7, 8};
    std::vector<long long> g = sosDP(f, n);
    std::cout << "g:";
    for (long long v : g) std::cout << " " << v;
    std::cout << '\n'; // g: 1 3 4 10 6 14 16 36
}

import java.util.Arrays;

public class SumOverSubsetsDP {
    static long[] sosDP(long[] f, int n) {
        long[] g = Arrays.copyOf(f, f.length);
        for (int i = 0; i < n; i++) {
            for (int mask = 0; mask < (1 << n); mask++) {
                if ((mask & (1 << i)) != 0) {
                    g[mask] += g[mask ^ (1 << i)];
                }
            }
        }
        return g;
    }

    public static void main(String[] args) {
        int n = 3;
        long[] f = {1, 2, 3, 4, 5, 6, 7, 8};
        long[] g = sosDP(f, n);
        System.out.println("g: " + Arrays.toString(g)); // g: [1, 3, 4, 10, 6, 14, 16, 36]
    }
}

The trace below follows f = [1, 2, 3, 4, 5, 6, 7, 8] (indexed by 3-bit mask) through each bit pass, matching the printed output exactly:

Spot-check mask = 111: its submasks are all eight masks 000–111, so g[111] must equal the sum of every f value, $1+2+\dots+8=36$ — which is exactly what both the bit-by-bit trace and the code print.

Zeta Transform, Möbius Transform, and OR/AND/XOR Connections

The transform SOS DP computes is called the zeta transform: g = ζ(f), where g[mask] sums f over all subsets of mask. It is the building block of OR-convolution: the array $h$ with $h[\text{mask}] = \sum_{a \mathbin{|} b = \text{mask}} f[a]\,g[b]$ can be computed by taking the zeta transform of $f$ and of $g$, multiplying the two transformed arrays pointwise, and inverse-transforming the result.

That inverse is the Möbius transform: it recovers f from g using inclusion–exclusion, by running the identical bit-by-bit loop with subtraction instead of addition:

# Given g (the zeta transform of f), recover f in place:
for i in range(n):
    for mask in range(1 << n):
        if mask & (1 << i):
            g[mask] -= g[mask ^ (1 << i)]
# g now holds the original f again (this is the Moebius / inverse transform)

Running this on the g = [1, 3, 4, 10, 6, 14, 16, 36] computed above peels bit 0, then bit 1, then bit 2, and returns exactly [1, 2, 3, 4, 5, 6, 7, 8] — the original f.

The same divide-and-conquer-over-bits pattern generalizes in two more directions. Summing over supermasks instead of submasks (mirror the trick: for each bit, propagate from the mask with the bit set into the mask without it) computes the analogous transform underlying AND-convolution. And processing bits with a different pairwise combine — add/subtract on the two halves rather than one-sided propagation — generalizes to the Fast Walsh–Hadamard Transform, which underlies XOR-convolution. FWHT is a more advanced technique left to a later point in the curriculum; it is named here only so the family of bit-by-bit transforms is recognizable when it appears.

8. Complexity Analysis

Every one of these bounds still has an exponential factor of $2^n$ or worse, so bitmask DP is only practical while $n$ stays small. As a rule of thumb, $2^{20} \approx 10^6$ is comfortable, $2^{22}$–$2^{24}$ is often the practical ceiling depending on the constant work per state, and beyond roughly $n = 25$ the table itself becomes too large to hold in memory regardless of how fast each transition is. This is a hard qualitative cutoff, not a tuning parameter: past it, the technique needs to be replaced — with meet-in-the-middle, a smaller or approximate state, or an entirely different algorithm — rather than optimized further.

9. Applications and Alternatives

The chief alternative to bitmask DP is not a different DP shape but a different exponent: when $n$ is too large for $2^n$, meet-in-the-middle splits the elements into two halves, enumerates $2^{n/2}$ possibilities for each half, and combines them, trading a squared-root improvement in the exponent for extra combination logic. When the state genuinely needs to track more than one number per subset, a plain array-indexed DP (as in the general Dynamic Programming Foundations lesson) is usually simpler and should be preferred unless the state really is "which elements are used."

10. Exercises and Mastery

Easy

1. Five cities 0–4 have cost matrix cost[i][j] of your choosing (symmetric, cost[i][i]=0). Trace dp[mask][last] for at least three intermediate masks by hand, then run the TSP code from Section 4 and confirm the minimum tour cost matches your trace.

Medium

1. Build a 4×4 cost matrix for the Assignment Problem where the optimal assignment is not the one obtained by greedily picking each worker's cheapest remaining task. Run the Assignment DP from Section 5 and verify it finds the true optimum, then show by brute force over all 24 permutations that no cheaper assignment exists.

Hard

1. A common competitive-programming pattern: given f[mask] for all $2^n$ masks, compute, for every mask, the maximum value of f[sub] over all submasks sub of mask (instead of the sum). Adapt the SOS DP transition in Section 7 — replace g[mask] += g[mask ^ (1<<i)] with a max update — and argue why the same $O(n \cdot 2^n)$ bound and the same bit-by-bit correctness argument still apply.

Review rhythm: tomorrow, rederive the TSP and Assignment DP recurrences from memory and explain in one sentence each why their state sizes differ; next week, implement SOS DP without looking it up and verify it against brute-force submask enumeration on a random small array; several weeks later, recognize a "bitmask as state" opportunity in an unrelated problem, and separately recognize a "sum/max over submasks for every mask" opportunity that calls for SOS DP instead of enumeration. Finally, teach someone the $3^n$ submask-enumeration argument using the three-choices-per-bit reasoning, not just the formula.

11. Summary Cheat Sheet

• Bitmask DP encodes "which elements have been used" as an integer state when $n$ is small (roughly $n \le 20$–22).
• TSP state: dp[mask][last], minimum cost to have visited exactly mask ending at last; $O(2^n \cdot n^2)$ time.
• Assignment state: dp[mask], next worker is popcount(mask); $O(n \cdot 2^n)$ time.
• Set Partition state: dp[mask], minimum valid subsets to exactly cover mask, trying every valid submask as the first piece.
• Submask enumeration: for (sub = mask; sub > 0; sub = (sub-1) & mask) visits every nonzero submask of mask; total work across all masks is $\Theta(3^n)$, from three independent choices per bit.
• SOS DP computes g[mask] = sum of f[sub] over all submasks, for every mask at once, in $O(n \cdot 2^n)$ by processing one bit at a time.
• SOS DP is the zeta transform; subtracting instead of adding gives the inverse Möbius transform; the same bit-by-bit idea generalizes to AND-convolution (supermasks) and, in more advanced form, to XOR-convolution via the Fast Walsh–Hadamard Transform.
• Past roughly $n=20$–22, replace the technique — meet-in-the-middle, a smaller state, or a different algorithm — rather than trying to optimize the constant factor.