When is a bitmask the right representation for subsets?

Category: DSA Patterns

Answer

When N <= ~22, bitmasks enumerate the 2^N subsets in O(2^N). The bit at position i is 1 if element i is in the subset. Bitwise AND tests intersection, OR tests union, XOR toggles membership. Use it for meet-in-the-middle, set cover, DP over subsets.

Concrete examples from the fca project context

Example 1

Iterate subsets: for mask in range(1<<N): for i in range(N): if mask >> i & 1: …

Example 2

Subset DP: dp[mask] = optimal answer using elements indicated by mask.

Example 3

Interview bitmask problem: partition array into two equal-sum subsets.

Data flow / flow chart

[a b c d]
  0000 0001 0010 0011 ... 1111  
  iterate all subsets in O(2^N)

Takeaway

Bitmask for small N, large subset count; prefer sum-of-subset DP when SUMs are bounded.