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)