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 fits | n at most about 20 |
|---|---|
| State | Integer mask of used items |
| Typical cost | O(2^n * n) or O(2^n * n^2) |
| Bit tools | mask >> 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
- Operator precedence: in many languages shift binds tighter than bitwise and, so write (mask >> i) & 1, or use parentheses.
- Use 1L in Java when n can exceed 31, or when masks are stored in long.
- Python lists of size 2^n are fine up to about 2^22, after which memory becomes the limit.
- Process masks in increasing numeric order so every submask has been computed before the larger mask.
- Skip unreachable states early, using a sentinel such as -1 or infinity.
Bitmask DP Interview Questions: questions with worked answers
1 Enumerate all subsets with bitmasks
easyEach 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.
pythondef subsets(nums): n = len(nums) return [[nums[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]javaList<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 Beautiful arrangements: count permutations with a divisibility rule
mediumNumbers 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.
pythondef 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]javaint 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 Can I win: a number picking game
mediumPlayers 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.
pythonfrom 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)javaMap<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 Partition into k subsets with equal sum
mediumThe 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.
pythondef 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] == 0javaboolean 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 Minimum number of work sessions
mediumTasks 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.
pythondef 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]javaint 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 Maximum compatibility score sum between students and mentors
mediumEach 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.
pythondef 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]javaint 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 Travelling salesman with Held-Karp
hardLet 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.
pythondef 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 bestjavalong 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 Count Hamiltonian paths in a graph
harddp[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.
pythondef 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])javalong 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 Number of ways to wear different hats
hardEach 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.
pythondef 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]javaint 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 Smallest sufficient team of people covering all skills
hardMap 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.
pythondef 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]javaList<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
- Cyclic sort pattern interview questions with worked solutions
- DFS (Depth-First Search) Interview Questions
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions