AntInLoop

Bitmask Dynamic Programming Code Implementations

Complete Bitmask Dynamic Programming code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.

Read Bitmask Dynamic Programming Guide · Launch Interactive Visualizer

C++ Implementation

// Bitmask DP Implementation in C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

class BitmaskDP {
public:
    // Traveling Salesman Problem with Bitmask DP
    static int tspBitmask(const std::vector<std::vector<int>>& graph) {
        int n = graph.size();
        std::vector<std::vector<int>> dp(1 << n, std::vector<int>(n, INT_MAX));
        
        // Base case: starting from node 0
        dp[1][0] = 0;
        
        // Try all possible subsets
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int last = 0; last < n; last++) {
                if (!(mask & (1 << last))) continue;
                
                int prevMask = mask ^ (1 << last);
                if (prevMask == 0) continue;
                
                for (int curr = 0; curr < n; curr++) {
                    if (prevMask & (1 << curr)) {
                        dp[mask][last] = std::min(dp[mask][last], dp[prevMask][curr] + graph[curr][last]);
                    }
                }
            }
        }
        
        // Find minimum cost to return to start
        int minCost = INT_MAX;
        for (int last = 1; last < n; last++) {
            minCost = std::min(minCost, dp[(1 << n) - 1][last] + graph[last][0]);
        }
        
        return minCost;
    }
    
    // Subset Sum with Bitmask
    static bool subsetSumBitmask(const std::vector<int>& nums, int target) {
        int n = nums.size();
        std::vector<bool> dp(1 << n, false);
        dp[0] = true;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (!dp[mask]) continue;
            
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i))) {
                    int newMask = mask | (1 << i);
                    if (newMask != mask) {
                        dp[newMask] = true;
                    }
                }
            }
        }
        
        // Check if any subset sums to target
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask]) {
                int sum = 0;
                for (int i = 0; i < n; i++) {
                    if (mask & (1 << i)) {
                        sum += nums[i];
                    }
                }
                if (sum == target) return true;
            }
        }
        
        return false;
    }
    
    // Maximum Independent Set with Bitmask
    static int maxIndependentSetBitmask(const std::vector<std::vector<bool>>& graph) {
        int n = graph.size();
        std::vector<int> dp(1 << n, 0);
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (isIndependent(mask, graph)) {
                dp[mask] = countBits(mask);
            } else {
                // Try removing one vertex at a time
                for (int i = 0; i < n; i++) {
                    if (mask & (1 << i)) {
                        dp[mask] = std::max(dp[mask], dp[mask ^ (1 << i)]);
                    }
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
    
private:
    static bool isIndependent(int mask, const std::vector<std::vector<bool>>& graph) {
        int n = graph.size();
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                for (int j = i + 1; j < n; j++) {
                    if ((mask & (1 << j)) && graph[i][j]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    
    static int countBits(int n) {
        int count = 0;
        while (n) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    
public:
    // Hamiltonian Path with Bitmask
    static bool hamiltonianPathBitmask(const std::vector<std::vector<bool>>& graph) {
        int n = graph.size();
        std::vector<std::vector<bool>> dp(1 << n, std::vector<bool>(n, false));
        
        // Base case: single vertex
        for (int i = 0; i < n; i++) {
            dp[1 << i][i] = true;
        }
        
        // Try all possible subsets
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int last = 0; last < n; last++) {
                if (!(mask & (1 << last))) continue;
                
                int prevMask = mask ^ (1 << last);
                if (prevMask == 0) continue;
                
                for (int curr = 0; curr < n; curr++) {
                    if ((prevMask & (1 << curr)) && graph[curr][last]) {
                        dp[mask][last] = dp[mask][last] || dp[prevMask][curr];
                    }
                }
            }
        }
        
        // Check if any vertex can be the end of Hamiltonian path
        for (int last = 0; last < n; last++) {
            if (dp[(1 << n) - 1][last]) {
                return true;
            }
        }
        
        return false;
    }
    
    // Assignment Problem with Bitmask
    static int assignmentProblemBitmask(const std::vector<std::vector<int>>& cost) {
        int n = cost.size();
        std::vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            int tasks = countBits(mask);
            for (int worker = 0; worker < n; worker++) {
                if (!(mask & (1 << worker))) {
                    int newMask = mask | (1 << worker);
                    dp[newMask] = std::min(dp[newMask], dp[mask] + cost[worker][tasks]);
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
    
    // Partition Problem with Bitmask
    static bool partitionProblemBitmask(const std::vector<int>& nums) {
        int n = nums.size();
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        
        if (totalSum % 2 != 0) return false;
        
        int target = totalSum / 2;
        std::vector<bool> dp(1 << n, false);
        dp[0] = true;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (!dp[mask]) continue;
            
            int currentSum = 0;
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    currentSum += nums[i];
                }
            }
            
            for (int i = 0; i < n; i++) {
                if (!(mask & (1 << i)) && currentSum + nums[i] <= target) {
                    dp[mask | (1 << i)] = true;
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
    
    // Performance comparison
    static void comparePerformance(const std::vector<std::vector<int>>& graph) {
        auto start = std::chrono::high_resolution_clock::now();
        int result1 = tspBitmask(graph);
        auto end = std::chrono::high_resolution_clock::now();
        auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
        
        std::cout << "TSP Bitmask: " << result1 << " (" << duration1.count() << " μs)" << std::endl;
    }
};

JAVA Implementation

// Bitmask DP Implementation in Java

import java.util.*;

public class BitmaskDP {
    // Traveling Salesman Problem with Bitmask DP
    public static int tspBitmask(int[][] graph) {
        int n = graph.length;
        int[][] dp = new int[1 << n][n];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
        
        // Base case: starting from node 0
        dp[1][0] = 0;
        
        // Try all possible subsets
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int last = 0; last < n; last++) {
                if ((mask & (1 << last)) == 0) continue;
                
                int prevMask = mask ^ (1 << last);
                if (prevMask == 0) continue;
                
                for (int curr = 0; curr < n; curr++) {
                    if ((prevMask & (1 << curr)) != 0) {
                        dp[mask][last] = Math.min(dp[mask][last], dp[prevMask][curr] + graph[curr][last]);
                    }
                }
            }
        }
        
        // Find minimum cost to return to start
        int minCost = Integer.MAX_VALUE;
        for (int last = 1; last < n; last++) {
            minCost = Math.min(minCost, dp[(1 << n) - 1][last] + graph[last][0]);
        }
        
        return minCost;
    }
    
    // Subset Sum with Bitmask
    public static boolean subsetSumBitmask(int[] nums, int target) {
        int n = nums.length;
        boolean[] dp = new boolean[1 << n];
        dp[0] = true;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (!dp[mask]) continue;
            
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0) {
                    int newMask = mask | (1 << i);
                    if (newMask != mask) {
                        dp[newMask] = true;
                    }
                }
            }
        }
        
        // Check if any subset sums to target
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask]) {
                int sum = 0;
                for (int i = 0; i < n; i++) {
                    if ((mask & (1 << i)) != 0) {
                        sum += nums[i];
                    }
                }
                if (sum == target) return true;
            }
        }
        
        return false;
    }
    
    // Maximum Independent Set with Bitmask
    public static int maxIndependentSetBitmask(boolean[][] graph) {
        int n = graph.length;
        int[] dp = new int[1 << n];
        
        // Check if subset is independent
        for (int mask = 0; mask < (1 << n); mask++) {
            if (isIndependent(mask, graph)) {
                dp[mask] = countBits(mask);
            } else {
                // Try removing one vertex at a time
                for (int i = 0; i < n; i++) {
                    if ((mask & (1 << i)) != 0) {
                        dp[mask] = Math.max(dp[mask], dp[mask ^ (1 << i)]);
                    }
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
    
private static boolean isIndependent(int mask, boolean[][] graph) {
        int n = graph.length;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                for (int j = i + 1; j < n; j++) {
                    if ((mask & (1 << j)) != 0 && graph[i][j]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
    
private static int countBits(int n) {
        int count = 0;
        while (n != 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
    
    // Hamiltonian Path with Bitmask
    public static boolean hamiltonianPathBitmask(boolean[][] graph) {
        int n = graph.length;
        boolean[][] dp = new boolean[1 << n][n];
        
        // Base case: single vertex
        for (int i = 0; i < n; i++) {
            dp[1 << i][i] = true;
        }
        
        // Try all possible subsets
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int last = 0; last < n; last++) {
                if ((mask & (1 << last)) == 0) continue;
                
                int prevMask = mask ^ (1 << last);
                if (prevMask == 0) continue;
                
                for (int curr = 0; curr < n; curr++) {
                    if ((prevMask & (1 << curr)) != 0 && graph[curr][last]) {
                        dp[mask][last] = dp[mask][last] || dp[prevMask][curr];
                    }
                }
            }
        }
        
        // Check if any vertex can be the end of Hamiltonian path
        for (int last = 0; last < n; last++) {
            if (dp[(1 << n) - 1][last]) {
                return true;
            }
        }
        
        return false;
    }
    
    // Assignment Problem with Bitmask
    public static int assignmentProblemBitmask(int[][] cost) {
        int n = cost.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            int tasks = countBits(mask);
            for (int worker = 0; worker < n; worker++) {
                if ((mask & (1 << worker)) == 0) {
                    int newMask = mask | (1 << worker);
                    dp[newMask] = Math.min(dp[newMask], dp[mask] + cost[worker][tasks]);
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
    
    // Partition Problem with Bitmask
    public static boolean partitionProblemBitmask(int[] nums) {
        int n = nums.length;
        int totalSum = Arrays.stream(nums).sum();
        if (totalSum % 2 != 0) return false;
        
        int target = totalSum / 2;
        boolean[] dp = new boolean[1 << n];
        dp[0] = true;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (!dp[mask]) continue;
            
            int currentSum = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    currentSum += nums[i];
                }
            }
            
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0 && currentSum + nums[i] <= target) {
                    dp[mask | (1 << i)] = true;
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
}

JAVASCRIPT Implementation

// Bitmask DP Implementation in JavaScript

// Traveling Salesman Problem with Bitmask DP
function tspBitmask(graph) {
  const n = graph.length;
  const dp = Array(1 << n).fill().map(() => Array(n).fill(Infinity));
  
  // Base case: starting from node 0
  dp[1][0] = 0;
  
  // Try all possible subsets
  for (let mask = 1; mask < (1 << n); mask++) {
    for (let last = 0; last < n; last++) {
      if (!(mask & (1 << last))) continue;
      
      const prevMask = mask ^ (1 << last);
      if (prevMask === 0) continue;
      
      for (let curr = 0; curr < n; curr++) {
        if (prevMask & (1 << curr)) {
          dp[mask][last] = Math.min(dp[mask][last], dp[prevMask][curr] + graph[curr][last]);
        }
      }
    }
  }
  
  // Find minimum cost to return to start
  let minCost = Infinity;
  for (let last = 1; last < n; last++) {
    minCost = Math.min(minCost, dp[(1 << n) - 1][last] + graph[last][0]);
  }
  
  return minCost;
}

// Subset Sum with Bitmask
function subsetSumBitmask(nums, target) {
  const n = nums.length;
  const dp = 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))) {
        const newMask = mask | (1 << i);
        if (newMask !== mask) {
          dp[newMask] = true;
        }
      }
    }
  }
  
  // Check if any subset sums to target
  for (let mask = 0; mask < (1 << n); mask++) {
    if (dp[mask]) {
      let sum = 0;
      for (let i = 0; i < n; i++) {
        if (mask & (1 << i)) {
          sum += nums[i];
        }
      }
      if (sum === target) return true;
    }
  }
  
  return false;
}

// Maximum Independent Set with Bitmask
function maxIndependentSetBitmask(graph) {
  const n = graph.length;
  const dp = Array(1 << n).fill(0);
  
  // Check if subset is independent
  function isIndependent(mask) {
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        for (let j = i + 1; j < n; j++) {
          if ((mask & (1 << j)) && graph[i][j]) {
            return false;
          }
        }
      }
    }
    return true;
  }
  
  // Try all subsets
  for (let mask = 0; mask < (1 << n); mask++) {
    if (isIndependent(mask)) {
      dp[mask] = countBits(mask);
    } else {
      // Try removing one vertex at a time
      for (let i = 0; i < n; i++) {
        if (mask & (1 << i)) {
          dp[mask] = Math.max(dp[mask], dp[mask ^ (1 << i)]);
        }
      }
    }
  }
  
  return dp[(1 << n) - 1];
}

// Count set bits in a number
function countBits(n) {
  let count = 0;
  while (n) {
    count += n & 1;
    n >>= 1;
  }
  return count;
}

// Hamiltonian Path with Bitmask
function hamiltonianPathBitmask(graph) {
  const n = graph.length;
  const dp = Array(1 << n).fill().map(() => Array(n).fill(false));
  
  // Base case: single vertex
  for (let i = 0; i < n; i++) {
    dp[1 << i][i] = true;
  }
  
  // Try all possible subsets
  for (let mask = 1; mask < (1 << n); mask++) {
    for (let last = 0; last < n; last++) {
      if (!(mask & (1 << last))) continue;
      
      const prevMask = mask ^ (1 << last);
      if (prevMask === 0) continue;
      
      for (let curr = 0; curr < n; curr++) {
        if ((prevMask & (1 << curr)) && graph[curr][last]) {
          dp[mask][last] = dp[mask][last] || dp[prevMask][curr];
        }
      }
    }
  }
  
  // Check if any vertex can be the end of Hamiltonian path
  for (let last = 0; last < n; last++) {
    if (dp[(1 << n) - 1][last]) {
      return true;
    }
  }
  
  return false;
}

// Assignment Problem with Bitmask
function assignmentProblemBitmask(cost) {
  const n = cost.length;
  const dp = Array(1 << n).fill(Infinity);
  dp[0] = 0;
  
  for (let mask = 0; mask < (1 << n); mask++) {
    const tasks = countBits(mask);
    for (let worker = 0; worker < n; worker++) {
      if (!(mask & (1 << worker))) {
        const newMask = mask | (1 << worker);
        dp[newMask] = Math.min(dp[newMask], dp[mask] + cost[worker][tasks]);
      }
    }
  }
  
  return dp[(1 << n) - 1];
}

// Partition Problem with Bitmask
function partitionProblemBitmask(nums) {
  const n = nums.length;
  const totalSum = nums.reduce((sum, num) => sum + num, 0);
  if (totalSum % 2 !== 0) return false;
  
  const target = totalSum / 2;
  const dp = Array(1 << n).fill(false);
  dp[0] = true;
  
  for (let mask = 0; mask < (1 << n); mask++) {
    if (!dp[mask]) continue;
    
    let currentSum = 0;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) {
        currentSum += nums[i];
      }
    }
    
    for (let i = 0; i < n; i++) {
      if (!(mask & (1 << i)) && currentSum + nums[i] <= target) {
        dp[mask | (1 << i)] = true;
      }
    }
  }
  
  return dp[(1 << n) - 1];
}

PYTHON Implementation

# Bitmask DP Implementation in Python

def tsp_bitmask(graph):
    n = len(graph)
    dp = [[float('inf')] * n for _ in range(1 << n)]
    
    # Base case: starting from node 0
    dp[1][0] = 0
    
    # Try all possible subsets
    for mask in range(1, 1 << n):
        for last in range(n):
            if not (mask & (1 << last)):
                continue
            
            prev_mask = mask ^ (1 << last)
            if prev_mask == 0:
                continue
            
            for curr in range(n):
                if prev_mask & (1 << curr):
                    dp[mask][last] = min(dp[mask][last], dp[prev_mask][curr] + graph[curr][last])
    
    # Find minimum cost to return to start
    min_cost = float('inf')
    for last in range(1, n):
        min_cost = min(min_cost, dp[(1 << n) - 1][last] + graph[last][0])
    
    return min_cost

def subset_sum_bitmask(nums, target):
    n = len(nums)
    dp = [False] * (1 << n)
    dp[0] = True
    
    for mask in range(1 << n):
        if not dp[mask]:
            continue
        
        for i in range(n):
            if not (mask & (1 << i)):
                new_mask = mask | (1 << i)
                if new_mask != mask:
                    dp[new_mask] = True
    
    # Check if any subset sums to target
    for mask in range(1 << n):
        if dp[mask]:
            subset_sum = sum(nums[i] for i in range(n) if mask & (1 << i))
            if subset_sum == target:
                return True
    
    return False

def max_independent_set_bitmask(graph):
    n = len(graph)
    dp = [0] * (1 << n)
    
    def is_independent(mask):
        for i in range(n):
            if mask & (1 << i):
                for j in range(i + 1, n):
                    if (mask & (1 << j)) and graph[i][j]:
                        return False
        return True
    
    def count_bits(n):
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count
    
    # Try all subsets
    for mask in range(1 << n):
        if is_independent(mask):
            dp[mask] = count_bits(mask)
        else:
            # Try removing one vertex at a time
            for i in range(n):
                if mask & (1 << i):
                    dp[mask] = max(dp[mask], dp[mask ^ (1 << i)])
    
    return dp[(1 << n) - 1]

def hamiltonian_path_bitmask(graph):
    n = len(graph)
    dp = [[False] * n for _ in range(1 << n)]
    
    # Base case: single vertex
    for i in range(n):
        dp[1 << i][i] = True
    
    # Try all possible subsets
    for mask in range(1, 1 << n):
        for last in range(n):
            if not (mask & (1 << last)):
                continue
            
            prev_mask = mask ^ (1 << last)
            if prev_mask == 0:
                continue
            
            for curr in range(n):
                if (prev_mask & (1 << curr)) and graph[curr][last]:
                    dp[mask][last] = dp[mask][last] or dp[prev_mask][curr]
    
    # Check if any vertex can be the end of Hamiltonian path
    for last in range(n):
        if dp[(1 << n) - 1][last]:
            return True
    
    return False

def assignment_problem_bitmask(cost):
    n = len(cost)
    dp = [float('inf')] * (1 << n)
    dp[0] = 0
    
    for mask in range(1 << n):
        tasks = bin(mask).count('1')
        for worker in range(n):
            if not (mask & (1 << worker)):
                new_mask = mask | (1 << worker)
                dp[new_mask] = min(dp[new_mask], dp[mask] + cost[worker][tasks])
    
    return dp[(1 << n) - 1]

def partition_problem_bitmask(nums):
    n = len(nums)
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False
    
    target = total_sum // 2
    dp = [False] * (1 << n)
    dp[0] = True
    
    for mask in range(1 << n):
        if not dp[mask]:
            continue
        
        current_sum = sum(nums[i] for i in range(n) if mask & (1 << i))
        
        for i in range(n):
            if not (mask & (1 << i)) and current_sum + nums[i] <= target:
                dp[mask | (1 << i)] = True
    
    return dp[(1 << n) - 1]

# Additional bitmask utilities
def get_subset_sum(mask, nums):
    return sum(nums[i] for i in range(len(nums)) if mask & (1 << i))

def get_subset_elements(mask, nums):
    return [nums[i] for i in range(len(nums)) if mask & (1 << i)]

def next_subset(mask, n):
    return (mask - 1) & ((1 << n) - 1)