Using Bitmask DP Pattern
1. Compressing State with Bitmasks
Bitmask dynamic programming (DP) is a technique used to optimize state representation in DP problems where the state space can be efficiently encoded using bits. This is particularly useful when dealing with subsets or combinations of elements, where each element can either be included or excluded.
| State Representation | Description | Example |
|---|---|---|
| Bitmask | A binary number where each bit represents the inclusion or exclusion of an element. | 1010 represents elements at indices 1 and 3 included, others excluded. |
| State Size | For n elements, the number of possible states is 2^n. |
For 4 elements, there are 2^4 = 16 possible states. |
Example: Subset Generation Using Bitmasks
const elements = ['A', 'B', 'C', 'D'];
const n = elements.length;
for (let mask = 0; mask < (1 << n); mask++) {
const subset = [];
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
subset.push(elements[i]);
}
}
console.log('Subset: ', subset);
}
Note: The expression
mask & (1 << i) checks if the i-th bit is set in mask.
Example: Counting Set Bits
function countSetBits(mask) {
let count = 0;
while (mask > 0) {
count += mask & 1;
mask >>= 1;
}
return count;
}
// Example usage
const mask = 0b1101; // Binary: 1101
console.log(countSetBits(mask)); // Output: 32. Implementing Traveling Salesman Problem
The Traveling Salesman Problem (TSP) can be solved efficiently using bitmask dynamic programming when the number of cities is small (typically up to 20). The idea is to use a bitmask to represent the set of visited cities and compute the minimum cost to reach each city from the starting point.
| State | Description | Transition |
|---|---|---|
| dp[mask][i] | Minimum cost to reach city i with the set of visited cities represented by mask |
For each city j not in mask, update dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + cost[i][j]) |
Example: TSP with 4 Cities
const cities = 4;
const cost = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
];
let dp = Array(1 << cities).fill().map(() => Array(cities).fill(Infinity));
dp[1][0] = 0;
for (let mask = 1; mask < (1 << cities); mask++) {
for (let u = 0; u < cities; u++) {
if ((mask & (1 << u)) === 0) continue;
for (let v = 0; v < cities; v++) {
if ((mask & (1 << v)) !== 0) continue;
const newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + cost[u][v]);
}
}
}
let minCost = Infinity;
for (let i = 1; i < cities; i++) {
minCost = Math.min(minCost, dp[(1 << cities) - 1][i] + cost[i][0]);
}
console.log(minCost); // Output: 80
Note: The bitmask approach is efficient for small inputs (≤ 20 cities) due to its exponential time complexity O(n × 2^n). For larger inputs, approximation or heuristic methods are preferred.
3. Solving Assignment Problems
Bitmask Dynamic Programming (DP) is particularly effective for solving assignment problems where we need to assign tasks to agents or resources optimally. These problems often involve minimizing cost or maximizing benefit while ensuring each task is assigned to exactly one agent.
| Problem | Description | Approach | Time Complexity |
|---|---|---|---|
| Task Assignment | Assigning n tasks to n agents such that each agent gets one task and total cost is minimized. | Use bitmask DP where each bit represents whether a task has been assigned. State: dp[mask] = minimum cost to assign tasks represented by bits in mask. |
O(n * 2^n) |
| Job Scheduling | Assigning jobs to workers with different capabilities and costs. | State: dp[mask] = minimum cost to schedule jobs represented by mask. |
O(n * 2^n) |
Example: Minimize Cost to Assign Tasks
const n = 3;
const cost = [
[10, 20, 30],
[40, 50, 60],
[70, 80, 90]
];
let dp = new Array(1 << n).fill(Infinity);
dp[0] = 0;
for (let mask = 0; mask < (1 << n); mask++) {
const count = mask.toString(2).split('1').length - 1;
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) === 0) {
const newMask = mask | (1 << i);
dp[newMask] = Math.min(dp[newMask], dp[mask] + cost[count][i]);
}
}
}
console.log(dp[(1 << n) - 1]); // Output: 150
Note: The bitmask
mask represents which tasks have already been assigned. For each state, we try assigning the next unassigned task to an agent and update the DP table accordingly.
4. Finding Hamiltonian Path
A Hamiltonian path visits each node in a graph exactly once. When using bitmask dynamic programming, we can efficiently explore all possible paths in a graph with up to 20 nodes.
| State | Description | Transition | Value |
|---|---|---|---|
| dp[mask][i] | Minimum cost to reach node i with the set of visited nodes represented by mask |
For each node j in mask, update dp[mask ∪ {i}][i] |
Cost of the path |
Example: Finding Minimum Cost Hamiltonian Path
const n = 4;
const graph = [
[0, 10, 15, 20],
[5, 0, 35, 25],
[10, 30, 0, 40],
[20, 25, 30, 0]
];
const dp = Array(1 << n).fill().map(() => Array(n).fill(Infinity));
dp[1][0] = 0;
for (let mask = 1; mask < (1 << n); mask++) {
for (let u = 0; u < n; u++) {
if ((mask & (1 << u)) === 0) continue;
for (let v = 0; v < n; v++) {
if ((mask & (1 << v)) !== 0) continue;
const newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + graph[u][v]);
}
}
}
let minCost = Infinity;
for (let i = 0; i < n; i++) {
minCost = Math.min(minCost, dp[(1 << n) - 1][i]);
}
console.log(minCost); // Output: 80
Note: The bitmask DP approach is efficient for small graphs (up to 20 nodes) and can be used to find the minimum cost Hamiltonian path or cycle.
5. Solving Subset Sum with Bitmask
The bitmask dynamic programming (DP) approach is a powerful technique for solving subset sum problems efficiently when the size of the set is small (typically up to 20 elements). It leverages bitmasks to represent subsets and uses bitwise operations for state transitions.
| Property | Description | Notes |
|---|---|---|
| Bitmask Representation | Each subset is represented as a bitmask where the i-th bit indicates whether element i is included in the subset. | For a set of size n, there are 2^n possible subsets. |
| State Definition | dp[mask] = true if subset represented by mask sums to a target value. | Can be extended to store the actual sum or subset elements. |
| Transition | For each element, update dp[mask] based on including or excluding the element. | Transition: dp[mask | (1 << i)] = dp[mask] || dp[mask | (1 << i)] |
Example: Subset Sum with Bitmask
function subsetSumWithBitmask(nums, target) {
const n = nums.length;
const dp = new Array(1 << n).fill(false);
dp[0] = true;
for (let mask = 0; mask < (1 << n); mask++) {
if (!dp[mask]) continue;
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) === 0) {
const newMask = mask | (1 << i);
dp[newMask] = true;
}
}
}
return dp[(1 << n) - 1];
}
// Example usage:
const nums = [3, 1, 2, 5];
const target = 6;
console.log(subsetSumWithBitmask(nums, target)); // true (subset [1, 2, 3] sums to 6)
Note: This approach has exponential time complexity O(2^n), but is efficient for small inputs (n ≤ 20). For larger inputs, consider using standard DP or backtracking with pruning.
6. Implementing Set Cover Problem
The Set Cover problem involves finding the minimum number of subsets from a collection that cover all elements in a universe. When using bitmask dynamic programming, each subset is represented as a bitmask, and the state represents which elements are covered.
| State | Description | Transition |
|---|---|---|
| dp[mask] | Minimum number of subsets needed to cover elements represented by the bitmask mask |
For each subset S, update dp[mask | S] if dp[mask] + 1 < dp[mask | S] |
Example: Set Cover with Bitmask DP
const universe = [1, 2, 3, 4];
const subsets = [
[1, 2],
[2, 3],
[3, 4],
[1, 4]
];
const n = universe.length;
const m = subsets.length;
// Convert universe to bitmask
const universeMask = (1 << n) - 1;
// Initialize dp array
const dp = Array(1 << n).fill(Infinity);
dp[0] = 0;
// Convert subsets to bitmask representation
const subsetMasks = subsets.map(subset => {
let mask = 0;
for (const elem of subset) {
const idx = universe.indexOf(elem);
mask |= (1 << idx);
}
return mask;
});
// Fill dp table
for (let mask = 0; mask < (1 << n); mask++) {
if (dp[mask] === Infinity) continue;
for (let i = 0; i < m; i++) {
const newMask = mask | subsetMasks[i];
dp[newMask] = Math.min(dp[newMask], dp[mask] + 1);
}
}
// Result is minimum subsets to cover entire universe
console.log(dp[universeMask]); // Output: 2 (subsets [1,2] and [3,4])
Note: The bitmask DP approach is efficient for small universes (≤ 20 elements) due to exponential state space.
7. Solving Partition Problem
The bitmask dynamic programming (DP) pattern is particularly useful for solving partition problems where we need to divide a set into two subsets with specific properties, such as equal sum or equal size.
| Problem | Description | Solution Approach | Time Complexity |
|---|---|---|---|
| Equal Sum Partition | Partition an array into two subsets with equal sum. | Use bitmask DP to iterate through all possible subsets and check if any subset sums to half of the total sum. | O(n * 2^n) |
| Subset Sum | Determine if a subset exists with a given sum. | Use bitmask DP to explore all subsets and track achievable sums. | O(n * 2^n) |
Example: Equal Sum Partition
function canPartition(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
const dp = new Array(1 << nums.length).fill(false);
dp[0] = true;
for (let mask = 0; mask < (1 << nums.length); mask++) {
if (!dp[mask]) continue;
for (let i = 0; i < nums.length; i++) {
if ((mask & (1 << i)) === 0) {
const newMask = mask | (1 << i);
const sum = getSum(mask, nums) + nums[i];
if (sum === target) return true;
dp[newMask] = true;
}
}
}
return false;
}
function getSum(mask, nums) {
let sum = 0;
for (let i = 0; i < nums.length; i++) {
if ((mask & (1 << i)) !== 0) sum += nums[i];
}
return sum;
}
Note: For large inputs, this approach is inefficient. Consider using a 1D DP array for better performance in subset sum problems.
8. Finding Shortest Hamiltonian Path
The Hamiltonian Path problem involves finding the shortest path that visits each node exactly once in a weighted graph. When using bitmask dynamic programming (DP), we can efficiently solve this problem for small graphs (up to ~20 nodes) by leveraging the state representation of subsets.
| State | Description | Transition | Time Complexity |
|---|---|---|---|
| dp[mask][u] | Minimum cost to reach node u having visited all nodes in the subset represented by mask |
For each node v not in mask, update dp[mask ∪ {v}][v] with min(dp[mask][u] + weight[u][v]) |
O(n × 2^n) |
Example: Shortest Hamiltonian Path using Bitmask DP
const n = 4;
const dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
];
let dp = Array(1 << n).fill().map(() => Array(n).fill(Infinity));
dp[1][0] = 0;
for (let mask = 1; mask < (1 << n); mask++) {
for (let u = 0; u < n; u++) {
if ((mask & (1 << u)) === 0) continue;
for (let v = 0; v < n; v++) {
if ((mask & (1 << v)) !== 0) continue;
let newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);
}
}
}
let minCost = Infinity;
for (let i = 0; i < n; i++) {
minCost = Math.min(minCost, dp[(1 << n) - 1][i]);
}
console.log(minCost); // Output: 80
Note: This approach is efficient for small graphs but becomes infeasible for large graphs due to exponential time complexity.
9. Implementing State Transitions
Bitmask Dynamic Programming (DP) is particularly useful for problems involving state transitions where each state can be represented as a bitmask. The key idea is to use bits to represent the presence or absence of elements in a set, and transitions between states are computed using bitmask operations.
| State Representation | Description | Example |
|---|---|---|
| Bitmask | Each bit represents whether an element is included in the current state. | 1010 represents elements 1 and 3 in a set of size 4. |
| State Transition | Transition from one bitmask to another using bitwise operations. | state & (state - 1) removes the rightmost set bit. |
Example: Subset Generation Using Bitmask
function generateSubsets(nums) {
const n = nums.length;
const result = [];
for (let mask = 0; mask < (1 << n); mask++) {
const subset = [];
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
subset.push(nums[i]);
}
}
result.push(subset);
}
return result;
}
// Example usage:
console.log(generateSubsets([1, 2, 3]));Example: Counting Subsets with Specific Properties
function countSubsetsWithSum(nums, target) {
const n = nums.length;
let count = 0;
for (let mask = 0; mask < (1 << n); mask++) {
let sum = 0;
for (let i = 0; i < n; i++) {
if (mask & (1 << i)) {
sum += nums[i];
}
}
if (sum === target) {
count++;
}
}
return count;
}
// Example usage:
console.log(countSubsetsWithSum([1, 2, 3, 4], 5)); // Output: 2
Note: The time complexity of bitmask DP is O(2^n * n), where n is the number of elements. This makes it suitable for small input sizes (n ≤ 20).
10. Solving Job Assignment
The bitmask dynamic programming (DP) pattern is particularly useful for solving job assignment problems where each job must be assigned to exactly one worker, and each worker can handle at most one job. This is a classic application of bitmask DP to optimize resource allocation.
| State Representation | Description | Usage |
|---|---|---|
| mask | A bitmask representing which jobs have been assigned to workers. | Used to track job assignments efficiently in O(1) time. |
Example: Assigning Jobs to Workers
const jobs = [10, 20, 30]; // Cost of assigning job to worker
const workers = [15, 25, 35]; // Cost of assigning worker to job
// Using bitmask DP to find minimum cost assignment
function minCostJobAssignment(jobs, workers) {
const n = jobs.length;
const dp = new Array(1 << n).fill(Infinity);
dp[0] = 0;
for (let mask = 0; mask < (1 << n); mask++) {
const assignedJobs = bitCount(mask);
for (let i = 0; i < n; i++) {
if ((mask & (1 << i)) === 0) {
const newMask = mask | (1 << i);
dp[newMask] = Math.min(dp[newMask], dp[mask] + jobs[assignedJobs] * workers[i]);
}
}
}
return dp[(1 << n) - 1];
}
function bitCount(mask) {
let count = 0;
while (mask > 0) {
count += mask & 1;
mask >>= 1;
}
return count;
}
console.log(minCostJobAssignment(jobs, workers)); // Output: 105
Note: The bitmask DP approach is efficient for small job sets (n ≤ 20) due to exponential state space growth. For larger problems, alternative algorithms like the Hungarian algorithm may be more appropriate.
11. Handling Constraint Satisfaction
| Constraint Type | Description | Implementation | Example |
|---|---|---|---|
| Exclusive | Only one of a set of options can be selected | Use bitmask to ensure only one bit is set | const mask = (1 << i) | (1 << j); // Only one of i or j can be set |
| Inclusive | At least one of a set of options must be selected | Ensure at least one bit is set in the mask | if (mask & ((1 << n) - 1)) { // At least one of n options is set } |
| Mutual Exclusion | Two or more options cannot be selected together | Check for overlap in bitmasks | if ((mask1 & mask2) === 0) { // No overlap between masks } |
| Dependency | One option requires another to be selected | Ensure required bits are set when dependent bits are set | if ((mask & requiredMask) === requiredMask) { // Required options are set } |
Example: Constraint Satisfaction in Bitmask DP
function countValidCombinations(n, constraints) {
let count = 0;
const total = 1 << n;
for (let mask = 0; mask < total; mask++) {
let valid = true;
for (const [type, condition] of constraints) {
if (type === 'exclusive') {
const bits = mask & condition;
if (bits & (bits - 1)) { // More than one bit set
valid = false;
break;
}
} else if (type === 'mutual') {
const bits = mask & condition;
if (bits !== 0 && bits !== condition) { // Not all or none
valid = false;
break;
}
} else if (type === 'dependency') {
const required = mask & condition.required;
const dependent = mask & condition.dependent;
if (dependent !== 0 && required === 0) {
valid = false;
break;
}
}
}
if (valid) count++;
}
return count;
}Note: The
countValidCombinations function evaluates all constraints for each possible bitmask and counts valid combinations.12. Optimizing Memory Usage
Note: Bitmask Dynamic Programming can lead to exponential memory usage due to the number of states. Optimization techniques are essential for practical applications.
| Technique | Description | Memory Impact | Applicable Use Cases |
|---|---|---|---|
| State Space Reduction | Use only necessary bits to represent states, avoiding full bitmask expansion. | Reduces memory from O(2^n) to O(k), where k is the number of relevant states. | When only a subset of bits are active or relevant in the problem domain. |
| Bitset Optimization | Use compact data structures like std::bitset or custom bit manipulation for faster access. |
Improves cache locality and reduces memory overhead. | For problems with fixed-size state representations (e.g., up to 64 bits). |
| Space-Time Trade-offs | Use memoization with hash tables or arrays to trade memory for faster lookups. | Can increase memory usage but reduce time complexity in some cases. | When frequent state lookups are required and performance is critical. |
| Iterative Deepening | Process states in increasing order of bitmask size to avoid storing all states at once. | Reduces peak memory usage by processing smaller states first. | For problems where state size varies significantly and full enumeration is not needed. |
Example: Reducing State Space
#include <vector>
#include <algorithm>
// Instead of storing all 2^N states, only store relevant ones
int bitmask_dp_optimized(const std::vector<int>& weights, int max_weight) {
const int n = weights.size();
std::vector<int> dp(max_weight + 1, 0);
for (int i = 0; i < n; ++i) {
// Process in reverse to avoid reusing updated values
for (int w = max_weight; w >= weights[i]; --w) {
dp[w] = std::max(dp[w], dp[w - weights[i]] + weights[i]);
}
}
return dp[max_weight];
}
Example: Bitset Optimization
#include <bitset>
// Use bitset for compact representation of states
const int MAX_N = 64;
std::bitset<MAX_N> visited;
// Efficiently check and set state bits
void mark_visited(int index) {
visited.set(index);
}
bool is_visited(int index) {
return visited.test(index);
}
Memory Optimization Strategies
- State Space Reduction: Limit the number of unique states by filtering out irrelevant bits or combinations.
- Bitset Usage: Leverage optimized bit manipulation libraries to reduce memory overhead and improve access speed.
- Iterative Deepening: Process states in stages to manage peak memory consumption.
- Memoization Trade-offs: Balance between memory usage and lookup performance based on problem constraints.