Bitmask state (Bit Manipulation Sub-pattern)

// A mask is a set: bit i = item i is in. n up to ~20.
//   in:  (mask >> i) & 1     add: mask | (1 << i)     size: __builtin_popcount(mask)
void forEachSubset(int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++)
            if ((mask >> i) & 1) { /* item i is in this subset */ }
    }
}

// Visit-all DP (TSP shape): dp[mask][last] = best cost to start at 0,
// visit exactly the items in mask, and stand at last.
int visitAll(const vector<vector<int>>& cost) {
    int n = cost.size(), FULL = (1 << n) - 1;
    const int INF = 1e9;
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;                             // only item 0 visited, standing at 0
    for (int mask = 1; mask <= FULL; mask++)  // smaller masks are always finished first
        for (int last = 0; last < n; last++) {
            if (dp[mask][last] == INF) continue;
            for (int nxt = 0; nxt < n; nxt++) {
                if ((mask >> nxt) & 1) continue;
                int nm = mask | (1 << nxt);
                dp[nm][nxt] = min(dp[nm][nxt], dp[mask][last] + cost[last][nxt]);
            }
        }
    int best = INF;
    for (int last = 0; last < n; last++) best = min(best, dp[FULL][last] + cost[last][0]);
    return n == 1 ? 0 : best;
}

// Every submask of mask (for "split a set into two parts" DPs): 3^n in total.
void forEachSubmask(int mask) {
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) { /* use sub */ }
}