Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Dynamic Programming

Bitmask Dynamic Programming

Written by Published

When a subproblem is identified by "which of these n things have I used", the state is a subset - and a subset of at most about twenty items fits neatly in a single integer.

A set as a number

Bit i set means item i is in the set. With n items there are 2ⁿ possible subsets, and each is just an integer from 0 to 2ⁿ − 1 - which makes them perfect array indices, and makes comparing or copying a state a single machine operation.

Working with subset masks

javascript

const n = 4

// Is item i in the set?
const has = (mask, i) => (mask & (1 << i)) !== 0

// Add and remove.
const add = (mask, i) => mask | (1 << i)
const remove = (mask, i) => mask & ~(1 << i)

// Every subset of n items.
for (let mask = 0; mask < (1 << n); mask++) {
  const members = []
  for (let i = 0; i < n; i++) if (has(mask, i)) members.push(i)
  if (mask < 5) console.log(mask, members)
}

const full = (1 << n) - 1     // all items present
console.log("full set:", full, full.toString(2))

The worked example

Travelling salesman: visit every city exactly once, ending anywhere, at minimum cost. Brute force is n! - hopeless past about ten cities. Bitmask DP is O(n² · 2ⁿ), which handles twenty comfortably.

The state is (visited, current): which cities have been visited, and where you are standing. Two different routes reaching the same pair are interchangeable from that point on, and that is the overlap DP exploits.

Travelling salesman with a bitmask

javascript

function shortestTour(dist) {
  const n = dist.length
  const SIZE = 1 << n
  // best[mask][city] = cheapest way to have visited mask, standing on city.
  const best = Array.from({ length: SIZE }, () => new Array(n).fill(Infinity))

  best[1][0] = 0   // start at city 0, only city 0 visited

  for (let mask = 1; mask < SIZE; mask++) {
    for (let city = 0; city < n; city++) {
      if (best[mask][city] === Infinity) continue
      if (!(mask & (1 << city))) continue

      for (let next = 0; next < n; next++) {
        if (mask & (1 << next)) continue          // already visited
        const nextMask = mask | (1 << next)
        const candidate = best[mask][city] + dist[city][next]
        if (candidate < best[nextMask][next]) {
          best[nextMask][next] = candidate
        }
      }
    }
  }

  return Math.min(...best[SIZE - 1])
}

const dist = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0],
]

// Cheapest route is 0 → 1 → 3 → 2: 10 + 25 + 30.
console.log(shortestTour(dist))  // 65

Knowing when it applies

  • n is small - usually stated as n ≤ 20, sometimes n ≤ 15. That ceiling is the hint.
  • The state genuinely is a set, where order does not matter but membership does.
  • Subproblems overlap: many different orders reach the same set.

2²⁰ is about a million states, which is fine. 2³⁰ is a billion, which is not - so if n can be large, bitmask DP is the wrong idea and the problem wants a greedy insight or a different formulation entirely.

Previous2D Dynamic ProgrammingNextGreedy Algorithms Explained