Autocoder

Bitmask DP Interview Questions

Last updated 2026-11-19

Bitmask dynamic programming stores a set of chosen items as the bits of an integer, so the state space is all subsets of a small collection. It turns exponential brute force over permutations into O(n * 2^n) or O(n^2 * 2^n), which is fast enough when n is at most about 20.

This page covers ten problems, from plain subset enumeration to Held-Karp and counting Hamiltonian paths. Each has Python and Java code, complexity and edge cases. Plain DP technique is in dynamic programming interview questions, and the earlier BFS bitmask problem is in BFS interview questions.

When it fitsn at most about 20
StateInteger mask of used items
Typical costO(2^n * n) or O(2^n * n^2)
Bit toolsmask >> i & 1, mask | 1 << i, popcount

The pattern and when to spot it

The strongest signal is a small constraint, typically n between 10 and 20, together with a question about assigning, ordering or covering. Such limits are a hint that the intended solution is exponential but better than n factorial. When the order of choices matters only through the set already chosen, a mask captures all the information needed.

The usual design is dp[mask] or dp[mask][last]. The number of set bits often doubles as the index of the next position or person, which saves a dimension, as in assigning students to mentors. Subset iteration, such as for sub = mask; sub; sub = (sub - 1) & mask, enumerates the submasks of a mask in O(3^n) overall. Memoised recursion on the mask is natural for game problems like Can I Win.

Details to watch

Bitmask DP Interview Questions: questions with worked answers

  1. 1

    Enumerate all subsets with bitmasks

    easy

    Each integer from 0 to 2^n - 1 is a subset: bit i set means element i is included. Loop over the masks and collect elements whose bit is set. This is the building block of every bitmask DP. It works while n is small, around 20 at most. Time O(n * 2^n), space O(2^n) output. Edge cases: empty array (one subset, the empty one), n beyond about 25 is too slow, duplicates produce duplicate subsets unless deduplicated.

    python
    def subsets(nums):
        n = len(nums)
        return [[nums[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]
    java
    List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> cur = new ArrayList<>();
            for (int i = 0; i < n; i++) if ((mask >> i & 1) == 1) cur.add(nums[i]);
            res.add(cur);
        }
        return res;
    }
  2. 2

    Beautiful arrangements: count permutations with a divisibility rule

    medium

    Numbers 1 to n go into positions 1 to n, and at each position either the number divides the position or the position divides the number. The mask records which numbers are used, and the next position is popcount(mask) + 1. dp[mask] counts valid ways to fill that many positions. Time O(n * 2^n), space O(2^n). Edge cases: n equal to 1 (1), n up to 15 for the usual constraint, checking both divisibility directions.

    python
    def count_arrangement(n):
        dp = [0] * (1 << n)
        dp[0] = 1
        for mask in range(1 << n):
            if not dp[mask]:
                continue
            pos = bin(mask).count('1') + 1
            for i in range(1, n + 1):
                if not mask >> (i - 1) & 1 and (i % pos == 0 or pos % i == 0):
                    dp[mask | 1 << (i - 1)] += dp[mask]
        return dp[(1 << n) - 1]
    java
    int countArrangement(int n) {
        int[] dp = new int[1 << n];
        dp[0] = 1;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == 0) continue;
            int pos = Integer.bitCount(mask) + 1;
            for (int i = 1; i <= n; i++)
                if ((mask >> (i - 1) & 1) == 0 && (i % pos == 0 || pos % i == 0))
                    dp[mask | 1 << (i - 1)] += dp[mask];
        }
        return dp[(1 << n) - 1];
    }
  3. 3

    Can I win: a number picking game

    medium

    Players alternately pick an unused number from 1 to m, adding it to a running total, and the one who reaches the target wins. The state is the mask of used numbers, since the total follows from it. A state is winning if some pick either reaches the target or leaves the opponent in a losing state. Memoise on the mask. Time O(2^m * m), space O(2^m). Edge cases: target at most 0 (first player wins), sum of all numbers below the target (nobody can win, return false), m up to 20.

    python
    from functools import lru_cache
    def can_i_win(m, target):
        if target <= 0:
            return True
        if m * (m + 1) // 2 < target:
            return False
        @lru_cache(None)
        def win(mask, remaining):
            for i in range(1, m + 1):
                bit = 1 << (i - 1)
                if mask & bit:
                    continue
                if i >= remaining or not win(mask | bit, remaining - i):
                    return True
            return False
        return win(0, target)
    java
    Map<Integer, Boolean> memo = new HashMap<>();
    boolean canIWin(int m, int target) {
        if (target <= 0) return true;
        if (m * (m + 1) / 2 < target) return false;
        memo.clear();
        return win(m, 0, target);
    }
    private boolean win(int m, int mask, int remaining) {
        Boolean cached = memo.get(mask);
        if (cached != null) return cached;
        for (int i = 1; i <= m; i++) {
            int bit = 1 << (i - 1);
            if ((mask & bit) != 0) continue;
            if (i >= remaining || !win(m, mask | bit, remaining - i)) { memo.put(mask, true); return true; }
        }
        memo.put(mask, false);
        return false;
    }
  4. 4

    Partition into k subsets with equal sum

    medium

    The total must divide by k and no number may exceed the target total / k. Let dp[mask] be the sum of the chosen numbers modulo the target, or -1 if the mask is unreachable. From a reachable mask add any unused number that keeps the current bucket within the target. The answer is whether the full mask is reachable. Time O(n * 2^n), space O(2^n). Edge cases: total not divisible by k (false), a number larger than the target (false), k equal to 1 (true), n up to 16.

    python
    def can_partition_k(nums, k):
        total = sum(nums)
        if total % k:
            return False
        target = total // k
        if max(nums) > target:
            return False
        n = len(nums)
        dp = [-1] * (1 << n)
        dp[0] = 0
        for mask in range(1 << n):
            if dp[mask] < 0:
                continue
            for i in range(n):
                if not mask >> i & 1 and dp[mask] + nums[i] <= target:
                    dp[mask | 1 << i] = (dp[mask] + nums[i]) % target
        return dp[(1 << n) - 1] == 0
    java
    boolean canPartitionK(int[] nums, int k) {
        int total = 0, mx = 0, n = nums.length;
        for (int x : nums) { total += x; mx = Math.max(mx, x); }
        if (total % k != 0) return false;
        int target = total / k;
        if (mx > target) return false;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] < 0) continue;
            for (int i = 0; i < n; i++)
                if ((mask >> i & 1) == 0 && dp[mask] + nums[i] <= target)
                    dp[mask | 1 << i] = (dp[mask] + nums[i]) % target;
        }
        return dp[(1 << n) - 1] == 0;
    }
  5. 5

    Minimum number of work sessions

    medium

    Tasks must be finished in sessions of at most T hours, and each task fits in one session. Let dp[mask] hold a pair: the fewest sessions used and the load of the last session. Adding a task either fits in the current session or opens a new one. Comparing pairs lexicographically prefers fewer sessions, then a lighter last session. Time O(n * 2^n), space O(2^n). Edge cases: a task longer than T is invalid by the statement, a single task, all tasks fitting in one session.

    python
    def min_sessions(tasks, T):
        n = len(tasks)
        INF = (n + 1, 0)
        dp = [INF] * (1 << n)
        dp[0] = (1, 0)
        for mask in range(1 << n):
            if dp[mask] == INF:
                continue
            s, load = dp[mask]
            for i in range(n):
                if mask >> i & 1:
                    continue
                cand = (s, load + tasks[i]) if load + tasks[i] <= T else (s + 1, tasks[i])
                nm = mask | 1 << i
                if cand < dp[nm]:
                    dp[nm] = cand
        return dp[(1 << n) - 1][0]
    java
    int minSessions(int[] tasks, int T) {
        int n = tasks.length;
        int[][] dp = new int[1 << n][];
        dp[0] = new int[]{1, 0};
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == null) continue;
            int s = dp[mask][0], load = dp[mask][1];
            for (int i = 0; i < n; i++) {
                if ((mask >> i & 1) == 1) continue;
                int[] cand = load + tasks[i] <= T ? new int[]{s, load + tasks[i]} : new int[]{s + 1, tasks[i]};
                int nm = mask | 1 << i;
                if (dp[nm] == null || cand[0] < dp[nm][0] || (cand[0] == dp[nm][0] && cand[1] < dp[nm][1])) dp[nm] = cand;
            }
        }
        return dp[(1 << n) - 1][0];
    }
  6. 6

    Maximum compatibility score sum between students and mentors

    medium

    Each student is paired with exactly one mentor, and the score of a pair is the number of matching answers. The mask marks mentors already used, and the student being assigned is the popcount of the mask. dp[mask] is the best total so far, and the answer is dp of the full mask. Time O(m * 2^m), space O(2^m). Edge cases: a single student, all scores zero, m up to 8 in the usual constraints where brute force over permutations also works.

    python
    def max_compatibility(students, mentors):
        m = len(students)
        score = [[sum(a == b for a, b in zip(s, t)) for t in mentors] for s in students]
        dp = [-1] * (1 << m)
        dp[0] = 0
        for mask in range(1 << m):
            if dp[mask] < 0:
                continue
            i = bin(mask).count('1')
            if i == m:
                continue
            for j in range(m):
                if not mask >> j & 1:
                    dp[mask | 1 << j] = max(dp[mask | 1 << j], dp[mask] + score[i][j])
        return dp[(1 << m) - 1]
    java
    int maxCompatibility(int[][] students, int[][] mentors) {
        int m = students.length;
        int[][] score = new int[m][m];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < students[i].length; k++)
                    if (students[i][k] == mentors[j][k]) score[i][j]++;
        int[] dp = new int[1 << m];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int mask = 0; mask < (1 << m); mask++) {
            if (dp[mask] < 0) continue;
            int i = Integer.bitCount(mask);
            if (i == m) continue;
            for (int j = 0; j < m; j++)
                if ((mask >> j & 1) == 0)
                    dp[mask | 1 << j] = Math.max(dp[mask | 1 << j], dp[mask] + score[i][j]);
        }
        return dp[(1 << m) - 1];
    }
  7. 7

    Travelling salesman with Held-Karp

    hard

    Let dp[mask][i] be the cheapest path that starts at city 0, visits exactly the cities in mask and ends at city i. Extend from i to an unvisited j with the edge cost. The tour cost is the best dp[full][i] plus the return edge to city 0. This replaces the factorial brute force with O(n^2 * 2^n). Time O(n^2 * 2^n), space O(n * 2^n). Edge cases: a single city (0), unreachable pairs as infinity, asymmetric distances, n up to about 20.

    python
    def tsp(dist):
        n = len(dist)
        INF = float('inf')
        full = 1 << n
        dp = [[INF] * n for _ in range(full)]
        dp[1][0] = 0
        for mask in range(full):
            if not mask & 1:
                continue
            for i in range(n):
                if dp[mask][i] == INF or not mask >> i & 1:
                    continue
                for j in range(n):
                    if not mask >> j & 1:
                        nm = mask | 1 << j
                        dp[nm][j] = min(dp[nm][j], dp[mask][i] + dist[i][j])
        best = min(dp[full - 1][i] + dist[i][0] for i in range(n))
        return best
    java
    long tsp(int[][] dist) {
        int n = dist.length, full = 1 << n;
        long INF = Long.MAX_VALUE / 4;
        long[][] dp = new long[full][n];
        for (long[] row : dp) Arrays.fill(row, INF);
        dp[1][0] = 0;
        for (int mask = 1; mask < full; mask += 2)
            for (int i = 0; i < n; i++) {
                if (dp[mask][i] >= INF || (mask >> i & 1) == 0) continue;
                for (int j = 0; j < n; j++)
                    if ((mask >> j & 1) == 0)
                        dp[mask | 1 << j][j] = Math.min(dp[mask | 1 << j][j], dp[mask][i] + dist[i][j]);
            }
        long best = INF;
        for (int i = 0; i < n; i++) best = Math.min(best, dp[full - 1][i] + dist[i][0]);
        return best;
    }
  8. 8

    Count Hamiltonian paths in a graph

    hard

    dp[mask][v] is the number of paths that visit exactly the vertices in mask and end at v. Start with dp[1 << v][v] = 1 for every v, and extend along edges to unvisited neighbours. Sum dp[full][v] over all v. Counting cycles needs an extra edge back to the start. Time O(n^2 * 2^n), space O(n * 2^n). Edge cases: a single vertex (1 path), disconnected graphs (0), directed versus undirected edges (undirected counts each path in both directions), result needing long.

    python
    def count_hamiltonian_paths(n, adj):             # adj[u] = list of neighbours
        full = (1 << n) - 1
        dp = [[0] * n for _ in range(1 << n)]
        for v in range(n):
            dp[1 << v][v] = 1
        for mask in range(1 << n):
            for v in range(n):
                if not dp[mask][v]:
                    continue
                for w in adj[v]:
                    if not mask >> w & 1:
                        dp[mask | 1 << w][w] += dp[mask][v]
        return sum(dp[full])
    java
    long countHamiltonianPaths(int n, List<List<Integer>> adj) {
        int full = (1 << n) - 1;
        long[][] dp = new long[1 << n][n];
        for (int v = 0; v < n; v++) dp[1 << v][v] = 1;
        for (int mask = 0; mask <= full; mask++)
            for (int v = 0; v < n; v++) {
                if (dp[mask][v] == 0) continue;
                for (int w : adj.get(v))
                    if ((mask >> w & 1) == 0) dp[mask | 1 << w][w] += dp[mask][v];
            }
        long total = 0;
        for (int v = 0; v < n; v++) total += dp[full][v];
        return total;
    }
  9. 9

    Number of ways to wear different hats

    hard

    Each of up to 10 people can wear some of up to 40 hats, and all must wear different hats. Mask over people, not hats: dp[mask] is the number of ways in which the people in mask already have hats. Process hats one at a time. For each hat, update masks in decreasing order so the hat is used by at most one person. Take results modulo 10^9 + 7. Time O(hats * 2^n * n), space O(2^n). Edge cases: a person with no hats (0 ways), a single person, descending mask order so that one hat is not used twice.

    python
    def number_ways(hats):
        MOD = 10**9 + 7
        n = len(hats)
        by_hat = {}
        for p, hs in enumerate(hats):
            for h in hs:
                by_hat.setdefault(h, []).append(p)
        full = (1 << n) - 1
        dp = [0] * (1 << n)
        dp[0] = 1
        for h, people in by_hat.items():
            for mask in range(full, -1, -1):
                if not dp[mask]:
                    continue
                for p in people:
                    if not mask >> p & 1:
                        dp[mask | 1 << p] = (dp[mask | 1 << p] + dp[mask]) % MOD
        return dp[full]
    java
    int numberWays(List<List<Integer>> hats) {
        final int MOD = 1_000_000_007;
        int n = hats.size();
        List<List<Integer>> byHat = new ArrayList<>();
        for (int h = 0; h <= 40; h++) byHat.add(new ArrayList<>());
        for (int p = 0; p < n; p++) for (int h : hats.get(p)) byHat.get(h).add(p);
        int full = (1 << n) - 1;
        long[] dp = new long[1 << n];
        dp[0] = 1;
        for (int h = 1; h <= 40; h++)
            for (int mask = full; mask >= 0; mask--) {
                if (dp[mask] == 0) continue;
                for (int p : byHat.get(h))
                    if ((mask >> p & 1) == 0) dp[mask | 1 << p] = (dp[mask | 1 << p] + dp[mask]) % MOD;
            }
        return (int) dp[full];
    }
  10. 10

    Smallest sufficient team of people covering all skills

    hard

    Map each required skill to a bit. dp maps a covered-skills mask to the smallest team that achieves it. For each person, combine them with every existing entry and keep the smaller team for the new mask. The answer is the entry for the full skill mask. With at most 16 skills the state space stays small. Time O(people * 2^skills), space O(2^skills * team size). Edge cases: a person with no relevant skill (adds nothing), a single person covering everything, ties between equal-size teams.

    python
    def smallest_team(req_skills, people):
        idx = {s: i for i, s in enumerate(req_skills)}
        full = (1 << len(req_skills)) - 1
        dp = {0: []}
        for p, skills in enumerate(people):
            pm = 0
            for s in skills:
                if s in idx:
                    pm |= 1 << idx[s]
            if pm == 0:
                continue
            for mask, team in list(dp.items()):
                nm = mask | pm
                if nm not in dp or len(dp[nm]) > len(team) + 1:
                    dp[nm] = team + [p]
        return dp[full]
    java
    List<Integer> smallestTeam(String[] reqSkills, List<List<String>> people) {
        Map<String, Integer> idx = new HashMap<>();
        for (int i = 0; i < reqSkills.length; i++) idx.put(reqSkills[i], i);
        int full = (1 << reqSkills.length) - 1;
        Map<Integer, List<Integer>> dp = new HashMap<>();
        dp.put(0, new ArrayList<>());
        for (int p = 0; p < people.size(); p++) {
            int pm = 0;
            for (String s : people.get(p)) if (idx.containsKey(s)) pm |= 1 << idx.get(s);
            if (pm == 0) continue;
            for (Map.Entry<Integer, List<Integer>> e : new ArrayList<>(dp.entrySet())) {
                int nm = e.getKey() | pm;
                List<Integer> cur = dp.get(nm);
                if (cur == null || cur.size() > e.getValue().size() + 1) {
                    List<Integer> team = new ArrayList<>(e.getValue());
                    team.add(p);
                    dp.put(nm, team);
                }
            }
        }
        return dp.get(full);
    }

Frequently asked questions

When should I use bitmask DP?

Use it when the input size is small, around 20 items, and the problem asks about choosing, ordering or covering with dependence on which items are used.

What is the complexity of the travelling salesman DP?

Held-Karp runs in O(n^2 * 2^n) time and O(n * 2^n) space, far better than the O(n!) brute force, but still limited to roughly 20 cities.

How do I check whether bit i is set?

Use (mask >> i) & 1, or mask & (1 << i). To set it use mask | (1 << i), and to clear it use mask & ~(1 << i).

Do interviews ask bitmask DP?

It appears in harder rounds and contest-style tests, usually in problems with small n. The online assessment guide describes how such tests are typically structured.

Related guides

More in DSA Interview Questions

See all in this section