Bitmask DP

The Intuition

Imagine you have 5 friends living in different cities, and you want to find the cheapest road trip that visits all of them. With 5 friends, there are only 32 possible combinations of "which friends have I visited so far." You can list every one of them: nobody visited, just friend 1, friends 1 and 3, friends 2, 3, and 5, all five, and so on. An integer can represent each combination by treating each bit as a friend. The number 22, which is 10110 in binary, means you've visited friends 2, 3, and 5 but not friends 1 and 4.

For each of those 32 subsets, you track the best cost to reach that state. dp[10110] stores the cheapest way to have visited exactly friends 2, 3, and 5. To figure out dp[11110] (adding friend 1 to the mix), you check: "what if I came from dp[10110] and drove to friend 1? What if I came from dp[11100] and drove to friend 1?" You take the minimum across all subsets that are one friend away from your target.

The reason bitmasks work so well here is that checking "have I visited friend i?" is a single operation: (mask >> i) & 1. Adding friend i to the visited set is mask | (1 << i). Removing friend i is mask & ~(1 << i). These operations are instant, and the mask itself is just a plain integer that serves as an array index. No sets, no sorted lists, no complex data structures. Just a number.

When to use

Problems with small input size (n <= 20) that require exploring all subsets or permutations, such as assignment problems, traveling salesman, subset partitioning, or game theory with turn-based choices.

When NOT to use

n > 20 (2^20 is already 1M states, beyond that is TLE), subsets have no ordering constraint (might simplify to regular DP), or problem has greedy property.

Pattern Recognition

The input size n is small (n <= 20), hinting at exponential state enumerationThe problem requires assigning items to groups or checking all permutationsYou need to track which elements have been used in a selection processThe problem involves partitioning a set into subsets with specific propertiesGame theory problems where each player picks from remaining itemsThe brute-force solution would enumerate all permutations or subsets

Variations:

Subset enumeration: Iterate over all subsets of a mask using sub = (sub - 1) & mask.
TSP-style: Track (mask, last_node) to find optimal Hamiltonian paths or cycles.
Partition into groups: Combine bitmask DP with a running sum to partition elements into equal subsets.

Edge Cases

n = 0 or empty input (no elements to process, return base case)
n = 1 (single element, trivial subset)
All elements are identical (multiple valid assignments may exist)
The target sum or partition is impossible (early termination check)
Overflow risk when n is close to 20 and additional state dimensions are used
The mask is fully set (all bits are 1), indicating all elements are processed
Negative values in the input that affect sum-based partition checks

Practice Problems

HardShortest Path Visiting All Nodes

MediumCan I Win

MediumPartition to K Equal Sum Subsets

Key Points

•Each bit in the mask represents whether an element has been used or visited
•State transitions flip individual bits to mark elements as included or excluded
•Practical only for small n (typically n <= 20) due to exponential state space
•Often combined with memoization or bottom-up DP on subsets
•Use (mask >> i) & 1 to check and mask | (1 << i) to set bit i

Code Template

 1  from functools import lru_cache
 2  
 3  def bitmask_dp_template(n, weights):
 4      """Generic bitmask DP: assign n items to minimize cost.
 5      Example: find minimum cost to visit all nodes.
 6      weights[i][j] = cost from item i to item j.
 7      """
 8      full_mask = (1 << n) - 1
 9  
10      @lru_cache(maxsize=None)
11      def dp(mask, last):
12          if mask == full_mask:
13              return 0  # all items processed
14  
15          result = float('inf')
16          for i in range(n):
17              if mask & (1 << i):
18                  continue  # already used
19              new_mask = mask | (1 << i)
20              cost = weights[last][i] + dp(new_mask, i)
21              result = min(result, cost)
22  
23          return result
24  
25      # Try starting from each item
26      ans = float('inf')
27      for start in range(n):
28          ans = min(ans, dp(1 << start, start))
29  
30      return ans
31  
32  def can_partition_k_subsets(nums, k):
33      """Check if nums can be partitioned into k subsets of equal sum."""
34      total = sum(nums)
35      if total % k != 0:
36          return False
37  
38      target = total // k
39      n = len(nums)
40      full_mask = (1 << n) - 1
41  
42      @lru_cache(maxsize=None)
43      def dp(mask, current_sum):
44          if mask == full_mask:
45              return True
46  
47          for i in range(n):
48              if mask & (1 << i):
49                  continue
50              new_sum = current_sum + nums[i]
51              if new_sum > target:
52                  continue
53              new_mask = mask | (1 << i)
54              next_sum = 0 if new_sum == target else new_sum
55              if dp(new_mask, next_sum):
56                  return True
57  
58          return False
59  
60      return dp(0, 0)

Common Mistakes

Exceeding memory or time limits by using bitmask DP with n > 20
Incorrect bit manipulation when checking or setting bits
Forgetting to handle the base case when the mask is 0 or fully set
Not considering that the order of selection may matter in some problems

Related Patterns

CrackingWalnuts

Dynamic ProgrammingTemplate 4 of 4

Dynamic ProgrammingAdvancedO(2^n * n) time, O(2^n) space