Dynamic Programming with Bitmasking

1. Introduction: The Traveling Salesperson

Imagine you are a delivery driver who must visit 15 different cities, ending back at your starting point. You want to find the absolute shortest possible route. This is the Traveling Salesperson Problem (TSP), one of the most famous NP-Hard problems in computer science.

If you use pure Brute Force/Backtracking, you must check every possible permutation of cities. For 15 cities, that's $15! \approx 1.3 \times 10^{12}$ routes. Your code will Time Out.

However, imagine you are halfway through a route. You are currently in City C, and you have visited {A, B, C}. Does it matter if the exact path you took was A -> B -> C or B -> A -> C? No! The only things that matter for the rest of the journey are:

1. What city you are currently in.
2. The set of cities you have already visited.

By caching this exact state (Current City, Set of Visited Cities), we can use Dynamic Programming to drop the time complexity from $O(N!)$ down to $O(N^2 \cdot 2^N)$. To represent a "Set of Visited Cities" efficiently as an array index, we use Bitmasking.

2. Core Concept: State Compression

In 1D and 2D DP, our state variables are simple integers (like an index or a weight limit). In Bitmask DP, one of our state variables is a Set. We cannot use a HashSet as an array index (dp[index][HashSet]), nor can we use a boolean[] array.

The Bitmask Trick: If $N \le 32$, we can represent an entire boolean[] array using a single 32-bit Integer!

• 000 (0) = No cities visited.
• 011 (3) = Cities 0 and 1 are visited.
• 101 (5) = Cities 0 and 2 are visited.
• 111 (7) = All 3 cities visited.

Now our DP table becomes incredibly simple: int[][] dp = new int[N][1 << N].

• Dimension 1 ($N$): The current city.
• Dimension 2 ($2^N$): The integer mask representing the visited cities.

3. Beginner Code Example: The Bitmask Utility Functions

Before writing a DP Bitmask algorithm, you must be completely fluent in manipulating the mask.

public class BitmaskUtils {
    // 1. Check if the i-th item is in the set
    public static boolean isVisited(int mask, int i) {
        return (mask & (1 << i)) != 0;
    }
    
    // 2. Add the i-th item to the set (Set the bit to 1)
    public static int addVisit(int mask, int i) {
        return mask | (1 << i);
    }
    
    // 3. Check if ALL items are visited (Are all N bits set to 1?)
    // For N = 3, we want 111 (binary) which is 7. (1 << 3) is 8. 8 - 1 = 7!
    public static boolean allVisited(int mask, int n) {
        return mask == (1 << n) - 1;
    }
}

4. Intermediate Code Example: Traveling Salesperson Problem (TSP)

Problem Statement: Given a 2D matrix graph[][] where graph[i][j] represents the distance from city i to city j, find the minimum distance to visit all cities exactly once and return to the starting city (City 0).

We will use Top-Down DP (Memoization) because Bottom-Up with bitmasks is conceptually much harder to write and iterate.

import java.util.Arrays;

public class TSP {
    private static final int INF = 99999999;
    
    public static int solveTSP(int[][] graph) {
        int n = graph.length;
        // dp[city][mask]
        int[][] dp = new int[n][1 << n];
        
        // Initialize DP table with -1 (uncalculated)
        for (int[] row : dp) Arrays.fill(row, -1);
        
        // Start at City 0. The mask is 1 (binary: 00...01), meaning City 0 is visited.
        return tsp(graph, 0, 1, n, dp);
    }
    
    private static int tsp(int[][] graph, int currentCity, int mask, int n, int[][] dp) {
        // Base Case: All cities have been visited
        if (mask == (1 << n) - 1) {
            // Return the distance from the last city back to the starting City 0
            return graph[currentCity][0]; 
        }
        
        // Memoization Check
        if (dp[currentCity][mask] != -1) {
            return dp[currentCity][mask];
        }
        
        int minDistance = INF;
        
        // Try visiting all other cities
        for (int nextCity = 0; nextCity < n; nextCity++) {
            // If the next city has NOT been visited yet
            if ((mask & (1 << nextCity)) == 0) {
                // MAKE CHOICE: Calculate distance to nextCity + recursively solve from nextCity
                int newMask = mask | (1 << nextCity);
                int currentDistance = graph[currentCity][nextCity] + tsp(graph, nextCity, newMask, n, dp);
                
                // Track minimum
                minDistance = Math.min(minDistance, currentDistance);
            }
        }
        
        // Save to cache and return
        return dp[currentCity][mask] = minDistance;
    }
}

Complexity Analysis:

• Time Complexity: $O(N^2 \cdot 2^N)$. The number of states is $N \cdot 2^N$. For each state, we loop over $N$ cities.
• Space Complexity: $O(N \cdot 2^N)$ for the DP table.

5. Advanced Code Example: Minimum XOR Sum (Assignment Problem)

Problem Statement: (LeetCode 1879) Minimum XOR Sum of Two Arrays. You are given two arrays nums1 and nums2 of length $N$. You must pair each element in nums1 with an element in nums2 such that the sum of their XOR values is minimized. Return the minimum sum. ($N \le 14$).

The Insight: We process nums1 in order (index from 0 to $N-1$). For nums1[index], we need to pick an unused element from nums2. We use a bitmask to track which elements in nums2 have already been used!

import java.util.Arrays;

public class MinXORSum {
    public int minimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        return solve(nums1, nums2, 0, 0, dp);
    }
    
    // index: which element in nums1 we are currently pairing
    // mask: tracks which elements in nums2 have been paired
    private int solve(int[] nums1, int[] nums2, int index, int mask, int[] dp) {
        // Base Case: All elements paired
        if (index == nums1.length) return 0;
        
        // Memoization check
        if (dp[mask] != -1) return dp[mask];
        
        int minSum = Integer.MAX_VALUE;
        
        // Try pairing nums1[index] with every available element in nums2
        for (int i = 0; i < nums2.length; i++) {
            // If nums2[i] is NOT used
            if ((mask & (1 << i)) == 0) {
                // The cost is the XOR value + the recursive cost of pairing the rest
                int currentXor = nums1[index] ^ nums2[i];
                int newMask = mask | (1 << i);
                
                minSum = Math.min(minSum, currentXor + solve(nums1, nums2, index + 1, newMask, dp));
            }
        }
        
        return dp[mask] = minSum;
    }
}

Complexity Analysis:

• Time Complexity: $O(N \cdot 2^N)$. There are $2^N$ states (the mask). In each state, we iterate $N$ times. (Wait, do we need index in the DP table? No! The index is directly tied to the number of 1s in the mask, so the mask uniquely identifies the state).
• Space Complexity: $O(2^N)$ for the DP array.

6. Common Mistakes Beginners Make

1. Incorrect DP Array Dimensions

   • The Mistake: int[][] dp = new int[n][n] for a bitmask problem.
   • Why it's wrong: The bitmask represents $2^N$ possible states, not $N$. The correct sizing is 1 << N.

2. Operator Precedence in Bitwise Logic

   • The Mistake: if (mask & 1 << i == 0)
   • Why it's wrong: == is evaluated before &. This evaluates to mask & (1 << i == 0), which fails to compile. ALWAYS wrap bitwise operations in parentheses: if ((mask & (1 << i)) == 0).

3. Applying Bitmask DP when $N$ is too large

   • The Mistake: Trying to use DP Bitmasking when $N = 50$.
   • Why it's wrong: $2^{50}$ is $1.12 \times 10^{15}$. No computer can allocate an array that large, nor compute it in time. DP Bitmasking is strictly for constraints where $N \le 20$. If $N$ is large, the problem usually requires a Greedy algorithm, Flow Network, or standard 1D/2D DP.

7. Interview Q&A

Q1: How do you identify a DP Bitmask problem in an interview? Answer: The biggest giveaway is the constraints. If $N \le 20$, and the problem asks for permutations, assignments, or "visiting all items" (TSP style), it is a 99% guarantee that it's a DP Bitmask problem.

Q2: Can DP Bitmasking be done Iteratively (Bottom-Up)? Answer: Yes, but it requires iterating the mask from 0 to 2^N - 1. Because $Mask = 3$ (011) naturally relies on $Mask = 1$ (001) and $Mask = 2$ (010), a simple for(int mask = 0; mask < (1 << n); mask++) loop mathematically guarantees that all subset dependencies are computed before the superset is computed. However, Top-Down is usually easier to conceptualize.

Q3: What if there are more than 32 elements? Can I use a long mask? Answer: You can use a 64-bit long to hold up to 64 states. But you cannot create an array of size $2^{64}$. It would require exabytes of RAM. DP Bitmasking physically hits a RAM limit around $N=25$.

8. Practice Problems

1. Minimum XOR Sum of Two Arrays (LeetCode 1879)
   • Goal: Master the standard assignment pattern.
2. Find the Shortest Superstring (LeetCode 943)
   • Hint: This is TSP disguised as a string problem! The "cities" are strings, and the "distance" is the overlap between string A and string B.
3. Matchsticks to Square (LeetCode 473)
   • Hint: Can be solved using DP Bitmask. State represents which matchsticks have been used.

9. Summary

• State Compression: Convert a boolean[] visited array into a single integer where the $i$-th bit represents the $i$-th element.
• The Constraint Tell: If you see $N \le 20$ on a hard problem, immediately think Bitmask DP.
• Top-Down Priority: Write these using Recursion + Memoization. It prevents computing mathematically unreachable states (which a blind Bottom-Up loop would waste time on).
• TSP Paradigm: The ultimate solution to visiting elements optimally. Instead of $O(N!)$, we achieve $O(N^2 \cdot 2^N)$.