MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Data Structures & Algorithms (DSA)  Module 14 – Dynamic programming

Bitmask DP: subsets as states

Use the bits of an integer as the set of items already chosen, solve the travelling salesperson problem with Held-Karp and see when 2ⁿ states fit.

  • Advanced
  • 35 minutes
  • Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0, quickjs 0.32.0, Java 25, Clang 21.0.0 and Go 1.27.1
  • By MySmartCoPilot
Free: Sets as integers · Held-Karp: a set and the last stop · The shortest tour of 12 spots · 3 more sections. With a pass: 3 in-depth parts and 3 interview answers, about 23 minutes.

What you will learn

  • Represent subsets as integers in DP states
  • Solve the travelling salesperson problem with Held-Karp
  • Estimate when 2^n states are feasible

Before you start

What you’ll learn · Before you start

What you will learn

  • Represent subsets as integers in DP states
  • Solve the travelling salesperson problem with Held-Karp
  • Estimate when 2^n states are feasible

Before you start

On this page

Bitmask DP stores a set inside a DP state as one integer, whose bit number i says whether item i belongs to the set. The 2ⁿ integers from 0 to 2ⁿ − 1 are exactly the subsets of n items, so they can index a table. Two shapes of state cover most problems: dp[mask] when only the set matters, as when tasks are handed out one at a time, and dp[mask][last] when the last item also matters, as on a route. The second shape is the Held-Karp algorithm for the travelling salesperson problem, published by Held and Karp in 1962 and found by Bellman the same year: the shortest round trip through n places in O(2ⁿ · n²) time, where trying every order costs (n − 1)! routes. Because 2²⁰ is about a million, 16 to 20 items is the usual limit.

Sets as integers

Five operations are all a bitmask DP needs. The examples use mask = 0b1011, the set of items 0, 1 and 3.

Operation Python Example
Is item i in the set? (mask >> i) & 1 item 2: 0, item 3: 1
Add item i mask | (1 << i) add item 2: 0b1111 = 15
Remove item i mask & ~(1 << i) remove item 1: 0b1001 = 9
How many items? mask.bit_count() 3
Every item of n (1 << n) - 1 n = 4: 0b1111 = 15

Removing an item clears a bit, which gives a smaller number, so every subset of a mask is numerically smaller than the mask. A loop that counts masks upwards therefore finishes every set before any set that contains it, and that is the only order a subset DP needs.

Held-Karp: a set and the last stop

A round trip starts at spot 0 and must visit every spot once before it returns. Once some spots have been visited, the rest of the trip depends on two things only: which spots are left and where the traveller stands. The order of the earlier visits no longer matters. So the state is dp[mask][last]: the shortest route that starts at spot 0, visits exactly the spots in mask and stops at last.

Eight sets of spots that contain spot 0, from {0} to {0, 1, 2, 3}, each with its mask; every arrow adds one spot and leads to a larger mask.{0}0001 = 1{0, 1}0011 = 3{0, 2}0101 = 5{0, 3}1001 = 9{0, 1, 2}0111 = 7{0, 1, 3}1011 = 11{0, 2, 3}1101 = 13{0, 1, 2, 3}1111 = 15

The sets of four spots that contain the start, as masks

Text description of the diagram

The diagram shows the eight sets of four spots that contain spot 0, in four rows by size, each labelled with its mask in binary and in decimal. Bit i of a mask is 1 when spot i is in the set.

  • Size 1: {0}, mask 0001 = 1.
  • Size 2: {0, 1} = 3, {0, 2} = 5 and {0, 3} = 9.
  • Size 3: {0, 1, 2} = 7, {0, 1, 3} = 11 and {0, 2, 3} = 13.
  • Size 4: {0, 1, 2, 3} = 15.

An arrow joins each set to every set with one more spot: {0} to all three sets of size 2, each set of size 2 to the two sets of size 3 that contain it, and each set of size 3 to the full set. Adding a spot sets a bit that was 0, so every arrow leads to a larger number, and visiting the masks in increasing order finishes every set before any set that contains it.

The route to (mask, last) arrived from some other spot prev of mask, so dp[mask][last] is the smallest dp[mask without last][prev] + d[prev][last]. The program writes it forwards instead: from every reachable state it tries each spot not yet in the mask. The answer is the smallest dp[all][last] + d[last][0], the trip home included. There are 2ⁿ · n states with up to n choices each, hence O(2ⁿ · n²) time and O(2ⁿ · n) memory.

The shortest tour of 12 spots

Twelve tourist spots, with travel times in minutes made up for practice, the same in both directions:

Held-Karp on 12 spots, checked against every order on the first 8 Python · tour/tour.py 
"""Held-Karp on 12 tourist spots with synthetic travel times, checked against trying every order on the first 8."""
import random
from itertools import permutations

SPOTS = ["Hotel", "Fort", "Museum", "Lake", "Market", "Temple", "Garden", "Gallery", "Bridge", "Tower", "Bazaar", "Station"]
rng = random.Random(12)
n = len(SPOTS)
minutes = [[0] * n for _ in range(n)]
for a in range(n):
    for b in range(a + 1, n):
        minutes[a][b] = minutes[b][a] = rng.randint(5, 40)  # synthetic travel times, the same both ways
INF = float("inf")


def held_karp(d):
    """The shortest round trip from spot 0 through every spot, and the tour itself."""
    n = len(d)
    full = (1 << n) - 1
    # dp[mask][last]: the shortest route that starts at 0, visits exactly the spots of mask and stops at last
    dp = [[INF] * n for _ in range(1 << n)]
    came = [[-1] * n for _ in range(1 << n)]
    dp[1][0] = 0  # mask 1 holds spot 0 alone
    for mask in range(1, 1 << n):  # increasing: every smaller set is finished before a set that contains it
        if not mask & 1:
            continue
        for last in range(n):
            here = dp[mask][last]
            if here == INF:
                continue
            for nxt in range(n):
                if mask >> nxt & 1:
                    continue
                bigger = mask | 1 << nxt
                if here + d[last][nxt] < dp[bigger][nxt]:
                    dp[bigger][nxt] = here + d[last][nxt]
                    came[bigger][nxt] = last
    best, last = min((dp[full][v] + d[v][0], v) for v in range(1, n)) if n > 1 else (0, 0)
    tour, mask = [], full
    while last != -1:  # walk the recorded choices back to the start
        tour.append(last)
        mask, last = mask & ~(1 << last), came[mask][last]
    return best, tour[::-1] + [0]


def every_order(d):
    n = len(d)
    return min(sum(d[a][b] for a, b in zip((0, *p), (*p, 0))) for p in permutations(range(1, n)))


best, tour = held_karp(minutes)
print("shortest round trip of 12 spots:", best, "minutes")
print(" -> ".join(SPOTS[v] for v in tour))
print(f"states: {2**n:,} sets x {n} last spots = {2**n * n:,}")
small = [row[:8] for row in minutes[:8]]
print("first 8 spots: Held-Karp", held_karp(small)[0], "minutes, every one of the 5,040 orders", every_order(small))

Output

shortest round trip of 12 spots: 117 minutes
Hotel -> Gallery -> Station -> Fort -> Market -> Bridge -> Garden -> Tower -> Museum -> Bazaar -> Lake -> Temple -> Hotel
states: 4,096 sets x 12 last spots = 49,152
first 8 spots: Held-Karp 110 minutes, every one of the 5,040 orders 110

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 tour.py

The best round trip takes 117 minutes, and following the recorded choices backwards from the last stop rebuilds it. The table has 49,152 states. On the first 8 spots the DP and a brute force over all 5,040 orders agree on 110 minutes; on all 12, the brute force would have 39,916,800 orders to try.

How large can n get?

The table compares the (n − 1)! orders a brute force tries with the 2ⁿ · n states and 2ⁿ · n² transition steps of Held-Karp.

n Orders States Steps
8 5,040 2,048 16,384
12 4.0 × 10⁷ 49,152 5.9 × 10⁵
16 1.3 × 10¹² 1.0 × 10⁶ 1.7 × 10⁷
20 1.2 × 10¹⁷ 2.1 × 10⁷ 4.2 × 10⁸
25 6.2 × 10²³ 8.4 × 10⁸ 2.1 × 10¹⁰

Every extra spot doubles the states and adds a little more per state, so the DP grows like 2ⁿ while the brute force grows like a factorial. Memory gives out about when time does: 20 spots already need 2 × 10⁷ entries. The same encoding serves other problems. To assign n tasks to n people, dp[mask] alone is enough, because the size of the mask says which task comes next. To split items into groups, such as tasks into working days, the DP walks the submasks of every mask, 3ⁿ steps in all.

Exercise: the shortest delivery round trip

The exercise asks for the shortest round trip through up to 16 delivery points, with travel times that may differ in the two directions.

Exercise · Hard · Python, JavaScript

The shortest round trip through every delivery point

A rider starts at point 0, must visit every delivery point exactly once and come back to point 0. dist[a][b] is the travel time from point a to point b, and it need not equal dist[b][a] (one-way streets). Write shortest_round_trip(dist) (JavaScript: shortestRoundTrip(dist)), which returns the length of the shortest such round trip, for 1 ≤ n ≤ 16 points. A single point needs no travel at all, so its answer is 0.

For [[0, 7, 12, 9], [7, 0, 5, 14], [12, 5, 0, 6], [9, 14, 6, 0]] the answer is 27: 0 → 1 → 2 → 3 → 0 takes 7 + 5 + 6 + 9. The tests also use two points with different times each way, a one-way loop where only one direction is cheap, 9 points checked against every order, the 12 tourist spots of the lesson and 13 generated points.

Python · Starter code · route.py 

def shortest_round_trip(dist):
    """The shortest route that starts at point 0, visits every point once and returns to point 0."""
    raise NotImplementedError("write shortest_round_trip")
The sample tests · test_route.py 
from itertools import permutations

from route import shortest_round_trip

SPOTS = [
    [0, 35, 22, 38, 27, 14, 29, 5, 28, 35, 22, 34],
    [35, 0, 19, 40, 5, 14, 33, 28, 15, 26, 18, 8],
    [22, 19, 0, 17, 9, 37, 26, 30, 10, 6, 8, 37],
    [38, 40, 17, 0, 19, 10, 32, 33, 12, 32, 13, 39],
    [27, 5, 9, 19, 0, 25, 40, 15, 8, 40, 15, 37],
    [14, 14, 37, 10, 25, 0, 10, 30, 31, 35, 35, 29],
    [29, 33, 26, 32, 40, 10, 0, 39, 6, 10, 17, 21],
    [5, 28, 30, 33, 15, 30, 39, 0, 27, 28, 29, 24],
    [28, 15, 10, 12, 8, 31, 6, 27, 0, 12, 21, 20],
    [35, 26, 6, 32, 40, 35, 10, 28, 12, 0, 26, 28],
    [22, 18, 8, 13, 15, 35, 17, 29, 21, 26, 0, 28],
    [34, 8, 37, 39, 37, 29, 21, 24, 20, 28, 28, 0],
]


def generated(n, seed, one_way=False):
    """n points with times from 5 to 40, the same in every language (a Lehmer generator)."""
    d, x = [[0] * n for _ in range(n)], seed
    for a in range(n):
        for b in range(n):
            if a == b or (not one_way and b < a):
                continue
            x = (x * 48271) % 2147483647
            d[a][b] = 5 + x % 36
            if not one_way:
                d[b][a] = d[a][b]
    return d


def every_order(d):
    return min(sum(d[a][b] for a, b in zip((0, *p), (*p, 0))) for p in permutations(range(1, len(d))))


def test_one_and_two_points():
    """a single point needs no travel; two points go there and back"""
    assert shortest_round_trip([[0]]) == 0
    assert shortest_round_trip([[0, 4], [6, 0]]) == 10


def test_four_points():
    """0 -> 1 -> 2 -> 3 -> 0 takes 7 + 5 + 6 + 9"""
    assert shortest_round_trip([[0, 7, 12, 9], [7, 0, 5, 14], [12, 5, 0, 6], [9, 14, 6, 0]]) == 27


def test_one_way_loop():
    """only the direction 0 -> 1 -> 2 -> 3 -> 0 is cheap"""
    assert shortest_round_trip([[0, 1, 9, 9], [9, 0, 1, 9], [9, 9, 0, 1], [1, 9, 9, 0]]) == 4


def test_nine_points_against_every_order():
    """9 points with one-way times, checked against all 40,320 orders"""
    d = generated(9, 77, one_way=True)
    assert shortest_round_trip(d) == every_order(d) == 102


def test_twelve_tourist_spots():
    """the 12 spots of the lesson"""
    assert shortest_round_trip(SPOTS) == 117


def test_thirteen_generated_points():
    """13 generated points"""
    assert shortest_round_trip(generated(13, 2028)) == 127

JavaScript · Starter code · route.mjs 

/** The shortest route that starts at point 0, visits every point once and returns to point 0. */
export function shortestRoundTrip(dist) {
  throw new Error('write shortestRoundTrip');
}
The sample tests · route.test.mjs 
import { test, assert } from 'mysmartcopilot:test';
import { shortestRoundTrip } from './route.mjs';

const SPOTS = [
  [0, 35, 22, 38, 27, 14, 29, 5, 28, 35, 22, 34],
  [35, 0, 19, 40, 5, 14, 33, 28, 15, 26, 18, 8],
  [22, 19, 0, 17, 9, 37, 26, 30, 10, 6, 8, 37],
  [38, 40, 17, 0, 19, 10, 32, 33, 12, 32, 13, 39],
  [27, 5, 9, 19, 0, 25, 40, 15, 8, 40, 15, 37],
  [14, 14, 37, 10, 25, 0, 10, 30, 31, 35, 35, 29],
  [29, 33, 26, 32, 40, 10, 0, 39, 6, 10, 17, 21],
  [5, 28, 30, 33, 15, 30, 39, 0, 27, 28, 29, 24],
  [28, 15, 10, 12, 8, 31, 6, 27, 0, 12, 21, 20],
  [35, 26, 6, 32, 40, 35, 10, 28, 12, 0, 26, 28],
  [22, 18, 8, 13, 15, 35, 17, 29, 21, 26, 0, 28],
  [34, 8, 37, 39, 37, 29, 21, 24, 20, 28, 28, 0],
];

/** n points with times from 5 to 40, the same in every language (a Lehmer generator). */
function generated(n, seed, oneWay = false) {
  const d = Array.from({ length: n }, () => new Array(n).fill(0));
  let x = seed;
  for (let a = 0; a < n; a++) {
    for (let b = 0; b < n; b++) {
      if (a === b || (!oneWay && b < a)) continue;
      x = (x * 48271) % 2147483647;
      d[a][b] = 5 + (x % 36);
      if (!oneWay) d[b][a] = d[a][b];
    }
  }
  return d;
}

/** Every order of the points after 0, tried. */
function everyOrder(d) {
  const rest = d.map((_, i) => i).slice(1);
  let best = Infinity;
  const walk = (at, left, total) => {
    if (!left.length) {
      best = Math.min(best, total + d[at][0]);
      return;
    }
    left.forEach((v, i) => walk(v, [...left.slice(0, i), ...left.slice(i + 1)], total + d[at][v]));
  };
  walk(0, rest, 0);
  return best;
}

test('a single point needs no travel; two points go there and back', () => {
  assert.equal(shortestRoundTrip([[0]]), 0);
  assert.equal(shortestRoundTrip([[0, 4], [6, 0]]), 10);
});

test('0 -> 1 -> 2 -> 3 -> 0 takes 7 + 5 + 6 + 9', () => {
  assert.equal(shortestRoundTrip([[0, 7, 12, 9], [7, 0, 5, 14], [12, 5, 0, 6], [9, 14, 6, 0]]), 27);
});

test('only the direction 0 -> 1 -> 2 -> 3 -> 0 is cheap', () => {
  assert.equal(shortestRoundTrip([[0, 1, 9, 9], [9, 0, 1, 9], [9, 9, 0, 1], [1, 9, 9, 0]]), 4);
});

test('9 points with one-way times, checked against all 40,320 orders', () => {
  const d = generated(9, 77, true);
  assert.equal(everyOrder(d), 102);
  assert.equal(shortestRoundTrip(d), 102);
});

test('the 12 spots of the lesson', () => {
  assert.equal(shortestRoundTrip(SPOTS), 117);
});

test('13 generated points', () => {
  assert.equal(shortestRoundTrip(generated(13, 2028)), 127);
});
A hint

Keep dp[mask][last]: the shortest route that starts at point 0, visits exactly the points whose bits are set in mask and stops at last. Start from dp[1][0] = 0 and go through the masks in increasing order; from each reachable state, try every point next not yet in the mask. At the end, add the trip from last back to point 0 and take the smallest total.

The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Self-check

Check yourself

5 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.

  1. Question 1 of 5 How many minutes does the shortest round trip of the 12 tourist spots take?

    Type a number.

    Show the answer

    Answer: 117 minutes

    The run prints 117 minutes, starting and ending at the Hotel. On the first 8 spots, Held-Karp and the brute force over all 5,040 orders both find 110, which is the check that the DP is right.

  2. Question 2 of 5 Which expression is 1 exactly when item i is in the set stored in mask?

    Choose one answer.

    Show the answer

    Answer: (mask >> i) & 1

    Shifting right by i moves bit i to the lowest place, and & 1 keeps only that bit. mask & i tests the bits of the number i, not bit number i.

  3. Question 3 of 5 Why does a loop over masks from 0 upwards compute every set before any set that contains it?

    Choose one answer.

    Show the answer

    Answer: Adding an item turns a 0 bit into 1, which always makes the number larger

    A set that contains mask has every bit of mask and at least one more, so it is a larger number. Smaller masks do not always have fewer items (mask 8 has one item, mask 7 has three), but the order is still safe, because only subsets need to come first.

  4. Question 4 of 5 How many states dp[mask][last] does Held-Karp have for 16 spots?

    Type a number.

    Show the answer

    Answer: 1048576

    2¹⁶ = 65,536 sets times 16 possible last spots gives 1,048,576 states, and each state tries up to 16 next spots, about 1.7 × 10⁷ transitions. Trying every order instead would mean 15! ≈ 1.3 × 10¹² routes.

  5. Question 5 of 5 For a DP over all subsets of n items with a time limit of a second or two, which n is the usual limit?

    Choose one answer.

    Show the answer

    Answer: About 16 to 20, since 2²⁰ is about a million sets

    The number of states doubles with each item. At 20 items there are about 10⁶ sets, and multiplied by n or n² that is already 10⁷ to 4 × 10⁸ steps; at 30 items there would be 10⁹ sets.

Held-Karp proved, its tours checked, and its time and memory measured Pro

A table of a million states earns trust only with a proof and a check. This part proves why the set and the last stop are enough, checks the DP and its rebuilt tours against a brute force on 200 random instances, and measures its time and memory from 12 to 18 spots.

In this part:

  • Why the set and the last stop are enough: the proof
  • Checked against every order on 200 instances
  • Time and memory, measured

1 runnable example (Python) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Assignment with one mask, and grouping with submasks in 3ⁿ steps Pro

Many bitmask problems need less state than a tour and some need more work per state. This part assigns ten tasks to ten volunteers with dp[mask] and compares it with all 3,628,800 assignments and a greedy rule, then packs twelve tasks into the fewest working days by walking submasks, and proves the 3ⁿ bound.

In this part:

  • Ten tasks, ten volunteers, one mask
  • When the order of the tasks may be fixed
  • Packing tasks into days with submasks
  • Why walking every submask costs 3ⁿ: the proof

1 runnable example (Python) · about 2 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Held-Karp in JavaScript, Java, C++ and Go, with flat tables and shifts that wrap Pro

In compiled languages the table becomes one flat array, which is smaller and faster than lists of lists, and the width of the integer that holds a mask starts to matter. This part runs Held-Karp in four more languages on the 12 spots and on 16 generated spots, and shows where shifts go wrong.

In this part:

  • JavaScript, as it runs in the browser
  • Java, C++ and Go, built and run
  • Shifts and widths: the mask must fit its integer
  • The lowest set bit, and removing an item

3 runnable examples (C++, Go, Java, JavaScript, Python) · about 3 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Interview questions

  1. Fresher to mid · Warm-up

    In a DP over subsets stored as bitmasks, why is it safe to process the masks in increasing numeric order, even though mask 8 has fewer items than mask 7?

    A subset DP only needs every subset of a mask to be finished before the mask itself, not every smaller set. A subset of mask has some of mask's bits and none of the others, so removing an item turns a 1 into a 0 and always gives a smaller number; equivalently, adding an item always gives a larger one. Counting from 0 to 2ⁿ − 1 therefore meets every subset of a mask before the mask. Mask 8 (one item) comes after mask 7 (three items), but 8 is not a subset of 7, so the order of the two does not matter. Processing by number of items would also work, and is useful when only two layers of sizes are kept in memory.

  2. Mid to senior

    Your Held-Karp solution for 20 cities is correct but runs out of memory in Python, where it keeps lists of lists. Estimate its memory, and say what you change to fit it in 256 MB without losing exactness.

    First step and follow-ups

  3. Fresher to mid

    Ten delivery agents and ten orders: cost[i][j] is the time agent j needs for order i. A greedy rule gives each order in turn the fastest free agent. Show why that can fail, and give an exact method that finishes well under a second.

    First step and follow-ups

  4. Senior to staff

    A rider must visit 14 pickup and drop points from a depot, and each drop may only happen after its pickup. How does Held-Karp change, and what does the rule do to the number of states?

    First step and follow-ups

Key takeaways

  • A mask stores a set in an integer: bit i says whether item i is in it, and every subset of a mask is a smaller number.
  • Held-Karp keeps dp[mask][last], the shortest route through mask that stops at last: O(2ⁿ · n²) time against (n − 1)! orders.
  • dp[mask] is enough when the size of the mask tells you what comes next, as in assignment.
  • About 16 to 20 items is the limit, because states double with every item and memory runs out with them.

References

Related tools

Programmer Calculator (Bitwise) Bitwise maths at a real bit width — with overflow, endianness and every base at once. Binary & Hex Calculator Carries and borrows column by column, two’s complement, overflow flags and bitwise ops. Python Online Compiler Real CPython in your browser — with stdin, files and a stop button.

Report a problem with this lesson