Submask DP

Submask DP

Submask DP is a bitmask technique where, for a fixed mask, we iterate through all of its submasks efficiently.

Core Trick: Iterate all submasks of a mask

For a mask m, this loop goes through all non-zero submasks of m:

If you also need submask 0, process it separately.

Why it works?

• s - 1 changes the lowest set bit and all bits after it
• & m removes bits not in the original mask
• so we stay inside submasks of m

Complexity Fact (very important)

If you run the submask loop for every mask, total complexity is:

$O(3^n)$

Reason: for each bit, there are 3 choices:

• not in mask
• in mask but not in submask
• in both mask and submask

Example: Partition a set into valid groups

Suppose:

• ok[s] tells whether subset s is a valid group
• We want minimum number of groups to cover mask m

Let:

$dp[m] = \text{minimum groups to cover } m$