Bitmask DP

// dp[mask][i] = best cost to have visited exactly the nodes in mask,
//               ending at node i
// mask has bit i set iff we've visited node i

const n = /* number of nodes */;
const INF = Infinity;
const dp = Array.from({length: 1<<n}, () => new Array(n).fill(INF));

// Base: start at node 0, only node 0 visited
dp[1][0] = 0; // mask = 0001 (only bit 0 set), at node 0, cost 0

for (let mask = 1; mask < (1<<n); mask++) {
    for (let u = 0; u < n; u++) {
        if (!(mask >> u & 1)) continue;  // u not in this mask
        if (dp[mask][u] === INF) continue;
        for (let v = 0; v < n; v++) {
            if (mask >> v & 1) continue;  // v already visited
            const newMask = mask | (1 << v);
            dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + cost[u][v]);
        }
    }
}

// Answer: visit all nodes (full mask), end anywhere
const fullMask = (1<<n) - 1;
return Math.min(...dp[fullMask]);

// Enumerate all non-empty subsets of 'mask' in O(3^n) total
for (let s = mask; s > 0; s = (s - 1) & mask) {
    // process subset s of mask
    // (s-1) & mask clears the lowest set bit of s and
    // removes all bits not in mask
}

// Example: split mask into two complementary parts
for (let s = mask; s > 0; s = (s-1) & mask) {
    const complement = mask ^ s; // mask XOR s = bits in mask but not in s
    dp[mask] = Math.min(dp[mask], f(s) + f(complement));
    if (s === 0) break; // handle s=0 separately if needed
}

// Why O(3^n)? Each element is in: mask but not s, mask and s, or not in mask
// → 3 choices per element → 3^n total work across all masks