Advanced Bit Manipulation: Bitmasks, Subsets, and State Compression

Bitmasks: Representing Sets with Integers

An $n$-element set has $2^n$ possible subsets. We can map each subset to an integer in the range $[0, 2^n - 1]$, where the $i$-th bit is 1 if the $i$-th element is included, and 0 otherwise.

Set {A, B, C} (n=3)
Mask  000 = Empty Set
      001 = {A}
      010 = {B}
      011 = {A, B}
      111 = {A, B, C}

Enumerating All Subsets

void enumerateSubsets(int[] nums) {
    int n = nums.length;
    for (int mask = 0; mask < (1 << n); mask++) {
        // 'mask' represents a unique subset
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 1) {
                // Element i is in the current subset
                System.out.print(nums[i] + " ");
            }
        }
        System.out.println();
    }
}

Enumerating Subsets of a Specific Mask

// Iterate through every sub-subset of 'mask'
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // sub is a non-empty sub-subset of mask
}
// Note: sub = 0 (empty set) is skipped; handle it manually if needed.

Why does (sub - 1) & mask work?

• sub - 1 flips the lowest set bit to 0 and all bits below it to 1.
• & mask forces the result to be a valid sub-subset of the original mask.
• This results in a decreasing sequence of integers, representing all sub-subsets.

State Compression DP

When a DP state represents a "collection" or "set," we use bitmasks as indices in our DP table. This converts set-based logic into efficient integer arithmetic.

Traveling Salesperson Problem (TSP)

dp[mask][i] = Min distance to visit all cities in mask, ending at city i.

public int tsp(int[][] dist) {
    int n = dist.length;
    int FULL_MASK = (1 << n) - 1;
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
    
    dp[1][0] = 0; // Start at city 0
    
    for (int mask = 1; mask <= FULL_MASK; mask++) {
        for (int u = 0; u < n; u++) {
            if (((mask >> u) & 1) == 0) continue; // u not in visited set
            
            for (int v = 0; v < n; v++) {
                if (((mask >> v) & 1) == 1) continue; // v already visited
                int nextMask = mask | (1 << v);
                dp[nextMask][v] = Math.min(dp[nextMask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }
    // Return to start
    int ans = Integer.MAX_VALUE;
    for (int i = 1; i < n; i++) ans = Math.min(ans, dp[FULL_MASK][i] + dist[i][0]);
    return ans;
}

Complexity: $O(2^N \cdot N^2)$. Feasible for $N \le 20$.

Partition to K Equal Sum Subsets (LeetCode 698)

public boolean canPartitionKSubsets(int[] nums, int k) {
    int sum = 0;
    for (int n : nums) sum += n;
    if (sum % k != 0) return false;
    int target = sum / k;
    
    int n = nums.length;
    int[] dp = new int[1 << n]; // dp[mask] = current bucket remainder
    Arrays.fill(dp, -1);
    dp[0] = 0;
    
    Arrays.sort(nums); // Pruning optimization
    
    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == -1) continue;
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 1) continue;
            if (dp[mask] + nums[i] > target) break; // Exceeds current bucket
            
            int nextMask = mask | (1 << i);
            dp[nextMask] = (dp[mask] + nums[i]) % target;
        }
    }
    return dp[(1 << n) - 1] == 0;
}

Smallest Sufficient Team (LeetCode 1125)

Find the smallest group of people that cover all required skills using bitmasks to represent skill sets.

public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
    int n = req_skills.length;
    Map<String, Integer> skillMap = new HashMap<>();
    for (int i = 0; i < n; i++) skillMap.put(req_skills[i], i);
    
    int[] dp = new int[1 << n];
    int[] parent = new int[1 << n];
    int[] memberUsed = new int[1 << n];
    Arrays.fill(dp, Integer.MAX_VALUE / 2);
    dp[0] = 0;
    
    for (int pIdx = 0; pIdx < people.size(); pIdx++) {
        int skillMask = 0;
        for (String s : people.get(pIdx)) {
            if (skillMap.containsKey(s)) skillMask |= (1 << skillMap.get(s));
        }
        
        // Iterate backwards to update states with the current person
        for (int mask = (1 << n) - 1; mask >= 0; mask--) {
            int nextMask = mask | skillMask;
            if (dp[mask] + 1 < dp[nextMask]) {
                dp[nextMask] = dp[mask] + 1;
                parent[nextMask] = mask;
                memberUsed[nextMask] = pIdx;
            }
        }
    }
    // Backtrack to find IDs
    List<Integer> ids = new ArrayList<>();
    int curr = (1 << n) - 1;
    while (curr > 0) {
        ids.add(memberUsed[curr]);
        curr = parent[curr];
    }
    return ids.stream().mapToInt(i -> i).toArray();
}

Technical Performance Table

Constraints Guide

• $N \le 20$: State compression DP is the primary candidate.
• Complexity: Usually $O(2^N \cdot N)$ or $O(2^N \cdot N^2)$. 筋