📝 Blog 9: DP with Bitmasking (Advanced State Compression) 🎭

Dynamic Programming combined with bitmasking allows us to handle problems where states are subsets of elements. Instead of tracking states with arrays, we compress the information into a bitmask integer (binary representation of chosen/un-chosen states).

This technique shines in combinatorial optimization problems like Traveling Salesman, Hamiltonian paths, partitioning, and subset DP.

🔑 Key Concepts

Bitmask Representation

Each bit in an integer represents whether an element is included or not.
Example: For n = 4, mask 1011 means elements {0,1,3} are chosen.

State Definition

dp[mask]: Best answer considering subset represented by mask.
dp[pos][mask]: Best answer ending at pos with visited nodes in mask.

Transitions

Add/remove an element by flipping a bit.
Iterate over all bits set/unset in a mask.

📌 Classic Problems & Patterns

1. Traveling Salesman Problem (TSP)

Find the shortest path visiting all cities exactly once and return to start.

class TSP {
    private static final int INF = 1_000_000;

    public int tsp(int[][] dist) {
        int n = dist.length;
        int N = 1 << n;
        int[][] dp = new int[n][N];

        // Initialize DP
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], INF);
        }
        dp[0][1] = 0; // start at city 0, visited mask = 000..1

        for (int mask = 1; mask < N; mask++) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) == 0) continue; // u not visited
                for (int v = 0; v < n; v++) {
                    if ((mask & (1 << v)) != 0) continue; // v already visited
                    int nextMask = mask | (1 << v);
                    dp[v][nextMask] = Math.min(dp[v][nextMask], dp[u][mask] + dist[u][v]);
                }
            }
        }

        int ans = INF;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans, dp[i][N-1] + dist[i][0]);
        }
        return ans;
    }
}

2. Partition into K Equal Sum Subsets

Check if an array can be partitioned into k subsets with equal sum.

class PartitionK {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) return false;
        int target = sum / k, n = nums.length;

        boolean[] dp = new boolean[1 << n];
        int[] subsetSum = new int[1 << n];

        dp[0] = true;

        for (int mask = 0; mask < (1 << n); mask++) {
            if (!dp[mask]) continue;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) continue; // already taken
                int nextMask = mask | (1 << i);
                if (dp[nextMask]) continue;
                if (nums[i] + subsetSum[mask] % target <= target) {
                    dp[nextMask] = true;
                    subsetSum[nextMask] = subsetSum[mask] + nums[i];
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}

3. Counting Hamiltonian Paths

class HamiltonianPaths {
    public int countHamiltonianPaths(int[][] graph) {
        int n = graph.length;
        int[][] dp = new int[1 << n][n];
        dp[1][0] = 1; // start at 0

        for (int mask = 1; mask < (1 << n); mask++) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) == 0) continue;
                for (int v = 0; v < n; v++) {
                    if ((mask & (1 << v)) != 0) continue;
                    if (graph[u][v] == 1) {
                        dp[mask | (1 << v)][v] += dp[mask][u];
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += dp[(1 << n) - 1][i];
        }
        return ans;
    }
}

4. Minimum XOR Sum of Two Arrays

class MinXORSum {
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            int i = Integer.bitCount(mask); // number of assigned elements
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) == 0) {
                    dp[mask | (1 << j)] = Math.min(dp[mask | (1 << j)],
                                                   dp[mask] + (nums1[i] ^ nums2[j]));
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}