Balanced DP

// 1. Two-way split: minimize |S1 - S2|
function minDiffPartition(nums) {
    const total = nums.reduce((a,b)=>a+b,0);
    // Bitset DP: which sums ≤ total/2 are achievable?
    let dp = 1n; // BigInt bitset
    for (const n of nums) dp |= dp << BigInt(n);
    const half = total >> 1;
    for (let s = half; s >= 0; s--)
        if ((dp >> BigInt(s)) & 1n) return total - 2 * s;
    return total; // shouldn't reach
}

// 2. k-way split: minimize maximum group sum (binary search + greedy)
function minMaxPartition(nums, k) {
    let lo = Math.max(...nums), hi = nums.reduce((a,b)=>a+b,0);
    const check = (limit) => {
        let groups = 1, cur = 0;
        for (const n of nums) {
            if (cur + n > limit) { groups++; cur = 0; }
            cur += n;
        }
        return groups <= k;
    };
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        check(mid) ? hi = mid : lo = mid + 1;
    }
    return lo;
}

// 3. k groups of equal sum (bitmask DP for small n)
function canPartitionKSubsets(nums, k) {
    const total = nums.reduce((a,b)=>a+b,0);
    if (total % k !== 0) return false;
    const target = total / k;
    const n = nums.length;
    const dp = new Array(1 << n).fill(false); dp[0] = true;
    const sums = new Array(1 << n).fill(0);
    for (let mask = 0; mask < (1 << n); mask++) {
        if (!dp[mask]) continue;
        for (let i = 0; i < n; i++) {
            if ((mask >> i) & 1) continue;
            const next = mask | (1 << i);
            const newSum = (sums[mask] + nums[i]) % target;
            if (sums[mask] + nums[i] <= target) {
                sums[next] = newSum;
                dp[next] = true;
            }
        }
    }
    return dp[(1 << n) - 1];
}