Posted on Sep 1

📝 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]; } }