9.11 Bitmask / Digit DP

Demo: Partition to K Equal Sum Subsets — LC 698 (Medium — Meta/LinkedIn High)

Statement (Demo): Given an integer array nums and an integer k, return whether it can be divided into k non-empty subsets with equal sums. Example: nums=[4,3,2,3,5,2,1], k=4 → true ([5], [1,4], [2,3], [2,3] — each sums to 5) | ⚡ nums.length ≤ 16

Approach: mask = which elements are already used. When the current bucket fills (curSum % target === 0), a new bucket starts. Memoize the result per mask — that turns exponential search into O(2ⁿ · n).

function canPartitionKSubsets(nums, k) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % k) return false;
  const target = total / k;
  nums.sort((a, b) => b - a);
  if (nums[0] > target) return false;
  const n = nums.length;
  const memo = new Map();
  const dfs = (mask, curSum) => {
    if (mask === (1 << n) - 1) return true; // every element used
    if (memo.has(mask)) return memo.get(mask);
    let ok = false;
    for (let i = 0; i < n && !ok; i++) {
      if (mask & (1 << i)) continue;
      if (curSum + nums[i] <= target)
        ok = dfs(mask | (1 << i), (curSum + nums[i]) % target);
    }
    memo.set(mask, ok);
    return ok;
  };
  return dfs(0, 0);
}

Complexity: Time O(2ⁿ · n), Space O(2ⁿ)