Course contentsShow
← Computer Science
Lesson 962 of 2,87222. Dynamic ProgrammingFree lesson

Bitmasking for Subset DP

Represent subsets as bitmasks to efficiently solve DP on small sets in exponential time.

Bitmasking for Subset DP

What you'll learn: How to use bitmasks to represent subsets and efficiently solve dynamic programming problems involving small sets.


The Core Challenge

When solving DP problems that involve subsets of a collection (like selecting items, visiting cities, or choosing team members), representing every possible subset can be tricky. If we have n elements, there are 2ⁿ possible subsets. For small n (typically ≤ 20), we can use bitmasks to represent these subsets compactly.

What's a Bitmask?

A bitmask is simply an integer where each bit (0 or 1) indicates whether an element is included in the subset. For example, with 4 elements:

  • 1011 in binary (11 in decimal) means elements at positions 0, 1, and 3 are included (reading right-to-left)
  • 0100 in binary (4 in decimal) means only element at position 2 is included

Analogy: Think of a light switch panel with n switches. Each switch being ON or OFF represents whether that item is in your subset.

Why Use This in DP?

Instead of storing DP states like dp[subset_array], you store dp[mask] where mask is an integer from 0 to 2ⁿ−1. This makes:

  • State indexing instant (direct array access)
  • Transition calculations efficient (bitwise operations)
  • Memory usage predictable

Common operations:

  • Check if element i is in mask: mask & (1 << i)
  • Add element i: mask | (1 << i)
  • Remove element i: mask & ~(1 << i)
  • Iterate through all subsets: loop from 0 to 2ⁿ−1

Key Takeaway: Bitmasking transforms subset DP problems into efficient integer operations, allowing you to solve problems on small sets (up to ~20 elements) by representing each subset as a single integer and using bitwise operations for state transitions.