Bitmasking for Subset and Permutation DP

Today's Concepts

1. The Core Idea: What is a Bitmask?
2. Bitmask DP Applied: The Traveling Salesman Problem (TSP)
3. An Interview-Style Problem: Maximizing Score with Pairings
4. Implementing a Top-Down Solution
5. Complexity, Trade-offs, and The Golden Rule for Interviews

Concept 1: The Core Idea: What is a Bitmask?

At its heart, bitmasking is a technique to use the binary representation of an integer to represent a set or a subset. This is a form of state compression.

Technical Explanation

Given n items, indexed from 0 to n-1, we can use an n-bit integer called a mask to represent any subset of these items.

• If the i-th bit of the mask is 1, it means the i-th item is included in the subset.
• If the i-th bit is 0, it means the i-th item is excluded.

For n=4 items {A, B, C, D} (indexed 3, 2, 1, 0), the subset {A, C} would be represented by the binary number 1010, which is the integer 10. The empty set is 0000 (0), and the set of all items is 1111 (15).

This compact representation allows us to use the mask as an index in our DP table, e.g., dp[mask], where mask uniquely identifies a subset of items that have been processed.

Metaphor: The Light Switch Panel

Think of a panel with n light switches, one for each item. A subset is simply a specific configuration of these switches. An 'on' switch means the item is in the subset; an 'off' switch means it's not. Instead of describing the state of every single switch ("switch 0 is on, switch 1 is off..."), you can represent the entire panel's state with a single number. This number is the bitmask. Changing the set (adding or removing an item) is as fast as flipping a switch—a single bitwise operation.

To effectively use bitmasks, you must be comfortable with bitwise operations. The following article provides a great overview and Python examples for these essential operations.

Concept 2: Bitmask DP Applied: The Traveling Salesman Problem (TSP)

The Traveling Salesman Problem is the canonical example of a problem that is computationally hard but can be solved optimally for small inputs using bitmask DP.

Technical Explanation

Problem: Given a set of n cities and the distances between every pair of cities, find the shortest possible tour that visits each city exactly once and returns to the origin city.

A brute-force solution would be to try all permutations of cities, which has a time complexity of $O(n!)$. This becomes infeasible very quickly (for n=15, 15! is over a trillion).

With bitmask DP, we can solve it in $O(n^2\cdot 2^n)$ time. While still exponential, this is a massive improvement and makes the problem tractable for n up to around 20.

• State Definition: Let dp[mask][i] be the minimum cost of a path that starts at a designated city (say, city 0), visits all cities specified in the mask, and ends at city i.

• Recurrence Relation: To calculate dp[mask][i], we consider all possible cities j that could have been the city visited just before i. City j must be in the set of visited cities represented by mask, but it cannot be city i itself.
  The path to j would have visited the cities in mask excluding i. Let's call this prev_mask = mask XOR (1 << i).
  So, to find dp[mask][i], we try all valid j's and find the minimum:

  $$dp[\text{mask}][i]=\underset{j\in \text{mask},j\ne i}{\min }\left(dp[\text{prev\_mask}][j]+\text{dist}[j][i]\right)$$

• Base Case: dp[1 << 0][0] = 0. This represents a path starting and ending at city 0, having only visited city 0, with a cost of 0.

The following video provides an outstanding, step-by-step explanation of this logic.

Implementation (Bottom-Up)

Here is a Python implementation that follows the logic from the video.

import math

def tsp_bitmask(dist_matrix):
    """
    Solves TSP using bitmask DP.
    Time Complexity: O(n^2 * 2^n)
    Space Complexity: O(n * 2^n)
    """
    n = len(dist_matrix)
    
    # dp[mask][i]: min cost to visit cities in mask, ending at city i
    dp = [[math.inf] * n for _ in range(1 << n)]
    
    # Base case: start at city 0, mask is 0...0001
    dp[1][0] = 0
    
    # Iterate over all subsets (masks) of cities
    for mask in range(1, 1 << n):
        # For each city 'u' that is the endpoint of the path defined by 'mask'
        for u in range(n):
            # If city 'u' is not in the current set of visited cities, skip
            if not (mask & (1 << u)):
                continue
                
            # From 'u', try to go to every other city 'v'
            for v in range(n):
                # We can't go to a city we've already visited, or stay at the same city
                if (mask & (1 << v)) or u == v:
                    continue
                
                # The new mask represents visiting city 'v' after the path to 'u'
                next_mask = mask | (1 << v)
                
                # Update the cost for the new path
                new_cost = dp[mask][u] + dist_matrix[u][v]
                dp[next_mask][v] = min(dp[next_mask][v], new_cost)
                
    # Final step: find the minimum cost tour by returning to the start city (0)
    final_mask = (1 << n) - 1  # Mask with all bits set (all cities visited)
    min_tour_cost = math.inf
    
    for i in range(1, n):
        # Cost of tour ending at 'i' + cost to return to start (0) from 'i'
        tour_cost = dp[final_mask][i] + dist_matrix[i][0]
        min_tour_cost = min(min_tour_cost, tour_cost)
        
    return min_tour_cost if min_tour_cost != math.inf else 0

# Example
distances = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(f"Minimum TSP cost: {tsp_bitmask(distances)}") # Expected: 80 (0 -> 1 -> 3 -> 2 -> 0)

Concept 3: An Interview-Style Problem: Maximizing Score with Pairings

While TSP is a classic, interview problems often present bitmask DP in less obvious forms. Let's analyze a problem from LeetCode: "Maximize Score After N Operations".

Problem: You are given an array nums of 2*n positive integers. You must perform n operations. In the i-th operation (1-indexed), you:

1. Choose two elements x and y from nums.
2. Receive a score of i * gcd(x, y).
3. Remove x and y from nums.
   Return the maximum score you can achieve after n operations.

Why Bitmask DP?

• The core of the problem is choosing pairs of numbers. This is a subset/permutation problem.
• The constraints are small (n <= 7, so 2*n <= 14). This is a huge hint! A complexity involving $2^{14}$ is acceptable.
• We need to keep track of which numbers have already been used. A bitmask is perfect for this.

This next video walks through how to derive the DP solution from scratch.

Concept 4: Implementing a Top-Down Solution

The video uses a top-down (memoized recursion) approach, which is often more intuitive for this type of problem. Let's formalize that implementation.

• State Definition: A function solve(mask) will return the maximum score achievable using the elements not yet picked (i.e., the elements corresponding to the 0s in the mask).

• State Transition:

  1. Inside solve(mask), first find which operation number this is. If k elements have been used (k = number of set bits in mask), then we have performed k/2 operations. This is operation number op = (k/2) + 1.
  2. Iterate through all pairs of unused elements (i, j).
  3. For each pair, the score for this step is op * gcd(nums[i], nums[j]).
  4. The total score for this path is that score plus the result of the recursive call with an updated mask: solve(new_mask), where new_mask has bits i and j set.
  5. We take the maximum over all possible pairs (i, j).

• Base Case: If the mask has all bits set, all numbers have been used. We can't make any more pairs, so the score is 0.

from math import gcd
from functools import lru_cache

def max_score(nums):
    """
    Solves 'Maximize Score After N Operations' using top-down DP with bitmasking.
    Time Complexity: O(m^2 * 2^m) where m = 2*n
    Space Complexity: O(2^m) for memoization
    """
    m = len(nums)
    n_ops = m // 2
    
    # memo[mask] stores the max score for the subproblem defined by mask
    memo = {}

    def solve(mask):
        if mask in memo:
            return memo[mask]
        
        # Count how many numbers have been used
        used_count = bin(mask).count('1')
        
        # If all numbers are used, we are done with this path
        if used_count == m:
            return 0
            
        # Determine the current operation number (1-indexed)
        op_num = (used_count // 2) + 1
        
        max_val = 0
        # Find the first unused number 'i'
        for i in range(m):
            if not (mask & (1 << i)):
                # Find the second unused number 'j'
                for j in range(i + 1, m):
                    if not (mask & (1 << j)):
                        # Create the new mask for the recursive call
                        new_mask = mask | (1 << i) | (1 << j)
                        
                        current_score = op_num * gcd(nums[i], nums[j])
                        
                        # Recurse on the remaining numbers
                        remaining_score = solve(new_mask)
                        
                        max_val = max(max_val, current_score + remaining_score)
        
        memo[mask] = max_val
        return max_val

    # Start with an empty mask (no numbers used)
    return solve(0)

# Example
nums = [1, 2, 3, 4, 5, 6]
print(f"Maximum score: {max_score(nums)}") # Expected: 14

Concept 5: Complexity, Trade-offs, and The Golden Rule for Interviews

Understanding when to use bitmask DP is as important as knowing how.

Complexity Analysis

• Time Complexity: The general formula is $O(\text{num\_states}\times \text{transition\_time})$.
  • For TSP: $O(2^n\cdot n^2)$. States: $2^n\cdot n$. Transition: From each state, we can iterate to n other cities.
  • For Max Score: $O(2^m\cdot m^2)$. States: $2^m$. Transition: From each state, we iterate through $O(m^2)$ pairs.
• Space Complexity: This is determined by the size of the DP table or memoization cache.
  • For TSP: $O(2^n\cdot n)$
  • For Max Score: $O(2^m)$

The Golden Rule

This complexity analysis leads to a critical interview heuristic:

If a problem involves finding an optimal solution on subsets, permutations, or assignments, and the number of elements n is very small (typically n <= 20), you should immediately consider Dynamic Programming with Bitmasking.

The small constraint is a deliberate signal from the interviewer that an exponential time complexity in n is acceptable and expected.

Conclusion

You've now unlocked one of the most powerful advanced DP techniques. By representing subsets as integers, you can solve a class of problems that would otherwise be computationally intractable.

Key Takeaways:

• State Compression: Bitmasks are a form of state compression, allowing you to encode a subset of n items into a single integer.
• The dp[mask] Pattern: The bitmask is used as the key index for your DP state, representing the subproblem on that subset. The state might also include the last element visited, e.g., dp[mask][i].
• Exponential but Feasible: Bitmask DP algorithms have exponential time complexity, but they are vastly better than factorial-time brute-force approaches.
• The Interview Signal: A small constraint (n <= 20) on a combinatorial problem is a strong hint to use bitmasking.

Preview of the Next Lesson:
We will shift gears away from dynamic programming's exhaustive search for optimality. In the next lesson, we will explore Greedy Algorithms. You'll learn how making the locally optimal choice at each step can sometimes lead to a globally optimal solution, and more importantly, you'll learn how to prove when such a strategy is correct.