const n = 4;  // 4 elements, indexed 0..3

// Check if element i is in subset mask
function has(mask, i) { return (mask >> i & 1) === 1; }

// Add element i to subset mask
function add(mask, i) { return mask | (1 << i); }

// Remove element i from subset mask
function remove(mask, i) { return mask & ~(1 << i); }

// Count elements in subset mask
function popcount(mask) { return mask.toString(2).split('1').length - 1; }

// Iterate over all subsets of n elements
for (let mask = 0; mask < (1 << n); mask++) {
  const elements = [];
  for (let i = 0; i < n; i++) {
    if (has(mask, i)) elements.push(i);
  }
  // mask 5 = 0101 → elements [0, 2]
}

// Full set mask
const FULL = (1 << n) - 1;  // 1111 for n=4

// TSP with Bitmask DP — O(2^n · n²) time, O(2^n · n) space
function tsp(cost) {
  const n = cost.length;
  const FULL = (1 << n) - 1;
  const INF = Infinity;

  // dp[mask][i] = min cost to visit all cities in mask, ending at city i
  const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(INF));
  dp[1][0] = 0;  // start at city 0, only city 0 visited (mask = 0001)

  for (let mask = 1; mask < (1 << n); mask++) {
    for (let i = 0; i < n; i++) {
      if (dp[mask][i] === INF) continue;
      if (!(mask & (1 << i))) continue;  // city i must be in mask

      // Try extending to city j
      for (let j = 0; j < n; j++) {
        if (mask & (1 << j)) continue;  // already visited j

        const nextMask = mask | (1 << j);
        dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + cost[i][j]);
      }
    }
  }

  // Find minimum: visit all cities then return to city 0
  let minCost = INF;
  for (let i = 1; i < n; i++) {
    if (dp[FULL][i] !== INF) {
      minCost = Math.min(minCost, dp[FULL][i] + cost[i][0]);
    }
  }

  return minCost;
}

const cost = [
  [0, 10, 15, 20],
  [10, 0, 35, 25],
  [15, 35, 0, 30],
  [20, 25, 30, 0]
];
console.log(tsp(cost)); // 80 (0→1→3→2→0: 10+25+30+15=80)

// Assignment Problem — O(2^n · n) time
function assignmentProblem(cost) {
  const n = cost.length;
  const INF = Infinity;
  const dp = new Array(1 << n).fill(INF);
  dp[0] = 0;  // no tasks assigned, no cost

  for (let mask = 0; mask < (1 << n); mask++) {
    if (dp[mask] === INF) continue;

    // Worker index = number of tasks already assigned = popcount(mask)
    const worker = mask.toString(2).split('1').length - 1;
    if (worker >= n) continue;

    // Assign worker to each unassigned task
    for (let task = 0; task < n; task++) {
      if (mask & (1 << task)) continue;  // already assigned
      const nextMask = mask | (1 << task);
      dp[nextMask] = Math.min(dp[nextMask], dp[mask] + cost[worker][task]);
    }
  }

  return dp[(1 << n) - 1];
}

const costs = [
  [9, 2, 7, 8],
  [6, 4, 3, 7],
  [5, 8, 1, 8],
  [7, 6, 9, 4]
];
console.log(assignmentProblem(costs)); // 13 (worker0→task1: 2, w1→task2: 3, w2→task2... optimal)

// Minimum Cost to Connect All Points (bitmask DP — for small n)
// Manhattan distance: |x1-x2| + |y1-y2|
function minCostConnectPoints(points) {
  const n = points.length;
  const dist = (i, j) =>
    Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);

  const INF = Infinity;
  // dp[mask][i] = min cost of MST spanning exactly the nodes in mask,
  //               with i being the last node connected
  const dp = Array.from({ length: 1 << n }, () => new Array(n).fill(INF));
  dp[1][0] = 0;  // start: only node 0 in spanning set

  for (let mask = 1; mask < (1 << n); mask++) {
    for (let i = 0; i < n; i++) {
      if (!(mask & (1 << i)) || dp[mask][i] === INF) continue;

      for (let j = 0; j < n; j++) {
        if (mask & (1 << j)) continue;  // already in spanning set

        const nextMask = mask | (1 << j);
        dp[nextMask][j] = Math.min(dp[nextMask][j], dp[mask][i] + dist(i, j));
      }
    }
  }

  const FULL = (1 << n) - 1;
  return Math.min(...dp[FULL]);
}

console.log(minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]])); // 20

// Iterate over all subsets of mask (including empty set)
// Time: O(3^n) total across all masks — each element is in 0, 1, or 2 subsets
function iterateSubsets(mask) {
  const subsets = [];
  for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
    subsets.push(sub);
    // (sub - 1) & mask: decrement sub but keep only bits that are in mask
    // This efficiently enumerates all non-empty subsets of mask
  }
  subsets.push(0);  // empty subset
  return subsets;
}

console.log(iterateSubsets(0b1010)); // subsets of {1, 3}
// 10 (0b1010), 8 (0b1000), 2 (0b0010), 0

// Application: partition into two complementary subsets
function canPartitionIntoEqualHalves(nums) {
  const n = nums.length;
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const half = total / 2;

  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 === half) return true;
  }
  return false;
}

// Example: count ways to tile a 2×n grid with 1×2 dominoes
// State: bitmask of which cells in current column are already "occupied"
//        (by a horizontal domino extending from the previous column)
function tilingWays(n) {
  const dp = new Map();
  dp.set(0, 1);  // 0 cells pre-occupied at start, 1 way

  for (let col = 0; col < n; col++) {
    const next = new Map();

    function fill(colMask, nextMask, row) {
      if (row === 2) {
        next.set(nextMask, (next.get(nextMask) || 0) + (dp.get(colMask) || 0));
        return;
      }

      if (colMask & (1 << row)) {
        // Current row in this column is occupied, skip
        fill(colMask, nextMask, row + 1);
      } else {
        // Place a vertical domino (fills this row only)
        fill(colMask, nextMask, row + 1);

        // Place a horizontal domino (fills this row in current AND next column)
        if (row + 1 < 2 && !(colMask & (1 << (row + 1)))) {
          // This is simplified — real profile DP is more complex for 2×n
        }
      }
    }

    // Simpler closed-form for 2×n tiling: fib(n+1)
    // dp[n] = dp[n-1] + dp[n-2]
  }

  // For 2×n tiling, answer is Fibonacci(n+1)
  if (n === 0) return 1;
  let a = 1, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

console.log(tilingWays(4)); // 5