algorithms.live
    DSA
    advanced

    Bitmask DP (State Compression)

    Software Engineer path · lesson 38 of 99
    time O(2^n × n)
    space O(2^n)

    2–4 cities; city 0 is the start. Symmetric distances read best.

    Try:
    1015203525300123
    end 0end 1end 2end 3000100110101011110011011110111110∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞
    From stateTarget stateBest tourImpossible state

    Start at city 0 with only city 0 visited: dp[0001][0] = 0.

    Code (running line highlighted)
    1. 1dp[{0}][0] = 0 # start at city 0
    2. 2for mask in increasing order, for last in mask:
    3. 3 for next not in mask:
    4. 4 m2 = mask | (1 << next)
    5. 5 dp[m2][next] = min(dp[m2][next], dp[mask][last] + d[last][next])
    6. 6answer = min over last of dp[all][last] + d[last][0]
    Transitions
    0 / 15
    Improvements
    0 / 14
    Invariant: dp[mask][c] = cheapest path from 0 visiting exactly the cities in mask, ending at c.

    Tap any element in the diagram to inspect its state at this step.

    1 / 17

    Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.

    Subsets as integers

    Sort

    Sort each bitmask expression by what it does to the subset.

    Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.

    Test membership

    Drop items here

    Add an element

    Drop items here

    Remove an element

    Drop items here
    6 pieces left to place

    Test your knowledge

    20 questions
    Question 1 of 20
    Score: 0

    How do you iterate over all subsets of a bitmask m?

    The short version

    Imagine tracking which cities a salesman has visited using light switches. Each switch ON/OFF represents visited/not visited. Instead of storing lists, you store a single number whose binary bits encode the entire state.

    In more depth

    Subsets as Numbers

    A bitmask of n bits can represent all 2^n subsets of n elements.

    Bit i = 1 means element i is included
    Bit i = 0 means element i is excluded

    Common Operations:

    Check if i in mask: mask & (1 << i)
    Add i to mask: mask | (1 << i)
    Remove i from mask: mask & ~(1 << i)
    Iterate subsets: for (s = m; s > 0; s = (s-1) & m)

    TSP Pattern:

    dp[mask][i] = min cost to visit cities in 'mask' ending at city i

    Key Gotchas:

    Works for n ≤ 20 (2^20 ≈ 1 million states)
    Don't forget the empty subset when iterating
    Watch for signed vs unsigned integer issues

    When to reach for this

    • Visit all nodes exactly once (TSP/Hamiltonian Path)
    • Select k items from n with complex constraints
    • n is small (≤ 20) and need to consider all subsets
    • Keywords: 'all possible subsets', 'assignment problem'

    Interview Questions

    Two Sigma
    Airbnb
    Microsoft
    Palantir
    Citadel
    Facebook
    Uber
    Bloomberg
    Google
    Amazon
    Two Sigma

    References & Further Reading

    Dynamic Programming with BitmaskingYouTube
    video
    Dynamic programmingWikipedia
    article
    Travelling salesman problemWikipedia
    article
    All Data Structures & Algorithms topics

    Love this visualization?

    Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.

    100% free • No credit card required