Bitmasking Dynamic Programming coding pattern
1. Introduction and Foundations
1.1 What is Bitmask DP?
Core Idea: Bitmask Dynamic Programming (Bitmask DP) is a specific type of dynamic programming where the state is represented, at least partially, by an integer whose individual bits signify the inclusion/exclusion or status of elements in a set or sequence. Each bit acts like a boolean flag.
Representation: If you have N items (indexed 0 to N-1), you can use an integer (often called a mask) from 0 to 2^N — 1. The j-th bit of the mask corresponds to the j-th item.
- If the
j-thbit is 1, it typically means thej-thitem is included, visited, processed, or “on”. - If the
j-thbit is 0, it typically means thej-thitem is excluded, not visited, unprocessed, or “off”.
1.2 Why and When to Use Bitmask DP?
Constraint: The most significant limiting factor is N (number of bits), the number of items being tracked by the mask. Since the number of states is 2^N (or 2^N * poly(N)), Bitmask DP is generally only feasible for small N, typically N <= 20–22. Sometimes up to N=25 is possible if the work done per state is very small.
When NOT to use:
- If N is large (e.g.,
N > 30), 2^N becomes too large for typical time limits (around 10⁸ operations per second). - Also, if the problem structure doesn’t naturally map to subsets/permutations of a small number of items.
1.4 Essential Bitwise Operations Recap (Tailored for DP)
Here are the crucial bitwise operations and how they relate to manipulating DP states represented by masks:
Convert int number to binary representation for given bits size
// Helper function to get binary string representation
string toBinaryString(int n, int num_bits) {
if (n == 0) return string(num_bits, '0');
string binary = "";
while (n > 0) {
binary = (n % 2 == 0 ? "0" : "1") + binary;
n /= 2;
}
// Pad with leading zeros if necessary
int padding = num_bits - binary.length();
if (padding > 0) {
binary = string(padding, '0') + binary;
}
return binary;
}In c++, we can also write same code as below
string toBinaryString(int n, int num_bits) {
stringstream ss;
// Iterate from the most significant bit down to 0
for (int i = num_bits - 1; i >= 0; --i) {
// Shift 'n' right by 'i' and mask with 1 to get the bit value
ss << ((n >> i) & 1);
}
return ss.str();
}Or with c++20
string toBinaryString(int n, int num_bits) {
// {:0{}b} means:
// 0 -> Pad with zeros
// {} -> Use the next argument (num_bits) for width
// b -> Binary format
return format("{:0{}b}", n, num_bits);
}Generate mask
// Example mask representing subset {1, 3} (items 1 and 3)
// Binary: 1010 (reading from right to left corresponds to index 0, 1, 2, 3)
// So, bit 1 and bit 3 are set.
int mask = (1 << 1) | (1 << 3); // 2 + 8 = 10 ~ 1010Checking the i-th bit (Is item i included?)
if ((mask >> i) & 1) {
cout << " - " << items[i] << " (index " << i << ")" << std::endl;
}Or
if (mask & (1 << i)) {
cout << " - " << items[i] << " (index " << i << ")" << std::endl;
}Setting the i-th bit (Add item i to the set)
new_mask = mask | (1 << i);
Unsetting the i-th bit (Remove item i from the set)
new_mask = mask & ~(1 << i);(Note: ~ is bitwise NOT)
Toggling the i-th bit
new_mask = mask ^ (1 << i);(Bitwise XOR)
Counting Set Bits (Size of the subset)
#include <bit> // Required for std::popcount (C++20)
#include <iostream>
using namespace std;
int main() {
unsigned int mask = 0b11010110; // Example mask (214 in decimal)
// The one-liner:
int set_bits_count = popcount(mask);
cout << "Set bits count: " << set_bits_count << endl; // Output: Set bits count: 5
return 0;
}Or using manual loop
int count = 0;
for (int i = 0; i < N; ++i) {
if ((mask >> i) & 1) {
count++;
}
}Finding the Least Significant Bit (LSB)
int lsb_value = mask & -mask;(Gives the value 2^k where k is the index of the LSB)
Iterating Through Set Bits (Elements in the subset)
for (int i = 0; i < N; ++i) {
if ((mask >> i) & 1) {
// Process item i, which is in the set represented by 'mask'
cout << "Item " << i << " is in the mask " << mask << endl;
}
}2. Bitmask DP on Subsets
This chapter focuses on problems where the core task is to find an optimal subset of items that satisfies certain conditions. The order in which items are chosen usually doesn’t matter, only the final composition of the subset. The DP state typically represents the subset itself.
Let’s solve few problems.
Problem: Finding maximum weight/value subset with constraints
Given N items, each with a value v[i] and a weight w[i]. Find a subset of items such that the total weight does not exceed W, and the total value is maximized.
Example#1:
Items: N = 3
Values v: {60, 100, 120}
Weights w: {10, 20, 30}
Capacity W: 50
Ans: 220Approach # Bitmask DP iterative each mask i.e. subset
This is the classic 0/1 Knapsack problem. While usually solved with dp[i][current_weight], it can be solved with bitmask DP if N is small. Let’s use Bitmask DP to solve this problem so that we can understand the concept.
- We can iterate
mask=1tomask=(1<<N) - For each mask, we can find out all the bit set to
1in their binary representation to figure out chosen items. - Each mask will gives the total weight. We can apply weight constraints to choose this mask or not.
Following is code for reference.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> weights, vector<int> values, int capacity ) {
int n = weights.size();
vector<int> dp(1<<n, -1);
dp[0] = 0; // No values for empty list
for (int mask =1; mask < (1<<n); mask++) {
int total_capacity = 0;
int total_value = 0;
// Iterate each bits of mask
for (int i=0; i < n; i++) {
// check if ith bit is set
if((mask & (1 << i)) != 0) {
total_capacity += weights[i];
total_value += values[i];
}
}
// check the constraints
if(total_capacity <= capacity) {
dp[mask] = total_value;
}
}
return *max_element(dp.begin(), dp.end());
}
int main() {
vector<int> values = {60, 100, 120};
vector<int> weights = {10, 20, 30};
int capacity = 50;
int ans = solve(weights, values, capacity);
cout <<"ans " <<ans <<endl;
return 0;
}1125. Smallest Sufficient Team
https://leetcode.com/problems/smallest-sufficient-team/description/
In a project, you have a list of required skills req_skills, and a list of people. The ith person people[i] contains a list of skills that the person has.
Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person.
- For example,
team = [0, 1, 3]represents the people with skillspeople[0],people[1], andpeople[3].
Return any sufficient team of the smallest possible size, represented by the index of each person. You may return the answer in any order.
It is guaranteed an answer exists.
Get Dilip Kumar’s stories in your inbox
Join Medium for free to get updates from this writer.
Example 1:
Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"],
people = [["algorithms","math","java"],
["algorithms","math","reactjs"],
["java","csharp","aws"],
["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]Approach# Use bitmask with bottom up dynamic programming
We can use mask to represent which skills are used. Our goal is to build mask as 2^m -1 i.e. choose all the required skills. Here m<=16 therefore max mask size is 2¹⁶ -1 which is feasible to store as integer number.
Since our goal is to find out which people are selected to build the team to match the target required skills therefore we can also use second mask to represent the team. Here n ≤ 60 therefore max mask size is 2⁶⁰ -1 which means we need long long size to store the mask.
For each people skill, instead of array, we can use integer mask to represent skills they have.
DP Transition
f(skill_mask) = ?Goal is to find out the smaller skill_mask when we remove the ith person.
The set smallerSkillsMask=skillsMask∖skillsMaskOfPerson[i], where ∖ denotes the set difference, contains the required skills that the ith person does not possess. The other team members must possess these skills.
We can apply following trick
smaller_skill_mask = skills_mask & ~skills_mask_of_person[i]Following is code for reference.
class Solution {
private:
long long bitCount(long long num) {
long long count = 0;
while (num > 0) {
count += (num % 2);
num /= 2;
}
return count;
}
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills,
vector<vector<string>>& people) {
int m = people.size(), n = req_skills.size();
// Preprocessing
unordered_map<string, int> skills_map;
for (int i = 0; i < n; i++) {
skills_map[req_skills[i]] = i;
}
vector<int> person_skill_mask(m);
for (int i = 0; i < m; i++) {
for (string skill : people[i]) {
person_skill_mask[i] |= 1 << skills_map[skill];
}
}
// dp of for mask 0...2^n-1, initialize choosing all people as invalid
// choice
vector<long long> dp(1 << n, (1LL << m) - 1);
// base case: no skills require no people
dp[0] = 0;
// Iterate each mask i.e. target skills
for (int skill_mask = 1; skill_mask < (1 << n); skill_mask++) {
// Try each people to see if we can build smaller skill mask if we
// remove this people
for (int i = 0; i < m; i++) {
int smaller_skill_mask = skill_mask & ~person_skill_mask[i];
if (smaller_skill_mask != skill_mask) {
long long people_mask = dp[smaller_skill_mask] | (1LL << i);
if (bitCount(people_mask) <
bitCount(dp[skill_mask])) {
dp[skill_mask] = people_mask;
}
}
}
}
long long answer_mask = dp[(1 << n) - 1];
vector<int> ans;
for (int i = 0; i < m; i++) {
if ((answer_mask >> i) & 1) {
ans.push_back(i);
}
}
return ans;
}
};3. Bitmask DP on Permutations and Paths
This chapter shifts focus from selecting subsets (where order doesn’t matter) to problems involving sequences, orderings, permutations, or paths where the order of elements is critical.
3.1 Representing Visited Elements/Nodes in a Sequence
The representation itself is identical to subset DP: an integer mask where the i-th bit indicates the status of the i-th element/node.
Meaning: In this context, if the i-th bit of mask is 1, it usually means element/node i has been visited or included in the current path or permutation being built. If the bit is 0, it hasn’t been visited yet.
Example: For N=4 nodes {0, 1, 2, 3}:
- Mask 0 (0000): No nodes visited yet.
- Mask 1 (0001): Only node 0 visited.
- Mask 6 (0110): Nodes 1 and 2 have been visited (perhaps in the order 1 -> 2 or 2 -> 1, the mask itself doesn’t store the order).
- Mask 15 (1111): All nodes visited.
3.2 State Definition: dp[mask][last_element]
This is the key difference compared to basic subset DP. Since the order matters, the cost or feasibility of adding the next element often depends directly on the current last element in the sequence or path.
State: dp[mask][i]
Meaning: Represents the optimal value (e.g., minimum cost, maximum value, number of ways) for a path/permutation that:
- Has visited exactly the set of elements/nodes represented by mask.
- The last element visited in this path/permutation was element i.
Constraint: For dp[mask][i] to be a valid and meaningful state, the i-th bit must be set in mask. If (mask >> i) & 1 is false, dp[mask][i] usually represents an impossible state.
Initialization: DP table entries are typically initialized to infinity (for minimization), negative infinity (for maximization), or 0 (for counting), depending on the problem. Impossible states should retain this initial value.
3.3 Canonical Problem: Traveling Salesperson Problem (TSP)
TSP is the classic example requiring this DP state structure.
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A
Problem: For a given weighted directed graph G(V,E), find the distance of the shortest route that meets the following criteria:
- It is a closed cycle where it ends at the same point it starts.
- It visits each vertex exactly once.
Example# 1
Input:
4 6
0 1 2
1 2 3
1 3 9
2 0 1
2 3 6
3 2 4
Output:
16Approach# Mapping to Bitmask DP
- Nodes: Cities 0 to N-1.
- Mask: Represents the set of cities visited so far.
- last_element: The last city visited in the current partial path.
- State: dp[mask][i] = Minimum cost of a path starting at city 0, visiting exactly the cities specified in mask, and ending at city i.
Base Case: The path starts at city 0. So, the state representing just visiting city 0 has cost 0.
- dp[1 << 0][0] = 0; (Mask 00…01, last city is 0)
Transition (Pull Approach): To calculate dp[mask][i]:
- We must have come from some city j.
- City j must be in the mask, j != i.
- The state before visiting city i was (prev_mask, j) where prev_mask = mask ^ (1 << i).
- The cost to reach dp[mask][i] via city j is dp[prev_mask][j] + cost[j][i].
- We want the minimum cost, so we take the minimum over all possible previous cities j.
Final Answer: After filling the DP table, we need to consider the cost of visiting all cities (mask = (1 << N) — 1) ending at any city i, and then adding the cost to return to the start city (city 0).
Following is code for reference.
#include <bits/stdc++.h>
using namespace std;
int INF = INT_MAX/2; // Use a safe infinity
int solve(vector<vector<int>> & graph) {
int n = graph.size();
int MASK_MAX = 1 << n;
vector<vector<int>> dp(MASK_MAX, vector<int>(n,INF));
// Base case: Starting from 0 node and reaching ending at 0
dp[1<<0][0] = 0;
// Iterate each visited city
for(int mask=1; mask < MASK_MAX; mask ++) {
// Try all cities
for(int i=0; i < n; i++) {
// check if this city is part of mask
if(mask & (1 << i)) {
// Get the previous mask
int prev_mask = mask ^ (1 << i);
// if prev mask is 0 then skip as it is already handled
if(prev_mask == 0) {
continue;
}
// Try reaching 'i' from any valid previous city 'j' in prev_mask
for(int j=0; j < n; j++) {
if(prev_mask & (1 << j)) {
// Check if the previous state was reachable
if(dp[prev_mask][j] != INF) {
dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + graph[j][i]);
}
}
}
}
}
}
// Find the answer
int target_mask = MASK_MAX -1;
int ans = INF;
for (int i=0; i < n; i++) {
ans = min(ans, dp[target_mask][i] + graph[i][0]);
}
return ans == INF ? -1: ans;
}
int main() {
int V, E;
cin >>V >>E;
vector<vector<int>> graph(V, vector<int>(V,INF));
for(int i=0; i < E; i++) {
int u,v,w;
cin >>u >>v>>w;
graph[u][v] = w;
}
int ans = solve(graph);
cout <<ans << endl;
return 0;
}More concepts related to DigitDP can also be explored.
- Bitmask DP for Assignment and Matching
- Sum Over Subsets (SOS) DP
- Profile DP (DP on Broken Profile)
Happy learning !!!
