Partition Equal Subset Sum (Bitset Variant)

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % 2) return false;
        int target = total / 2;
        bitset<10001> dp;
        dp[0] = 1;
        for (int x : nums) dp |= (dp << x);
        return dp[target];
    }
};

func canPartition(nums []int) bool {
    total := 0
    for _, x := range nums {
        total += x
    }
    if total%2 != 0 {
        return false
    }
    target := total / 2
    // Bitset over [0, 10000] — 157 uint64 words cover bit indices 0..10047.
    const words = 157
    var dp [words]uint64
    dp[0] = 1
    for _, x := range nums {
        // Shift dp left by x bits, then OR into dp.
        wordShift := x / 64
        bitShift := uint(x % 64)
        var shifted [words]uint64
        for i := words - 1; i >= 0; i-- {
            src := i - wordShift
            if src < 0 {
                break
            }
            v := dp[src] << bitShift
            if bitShift != 0 && src-1 >= 0 {
                v |= dp[src-1] >> (64 - bitShift)
            }
            shifted[i] = v
        }
        for i := 0; i < words; i++ {
            dp[i] |= shifted[i]
        }
    }
    return dp[target/64]&(uint64(1)<<uint(target%64)) != 0
}

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        dp = 1  # Python int as bitset; bit i set => sum i reachable.
        for x in nums:
            dp |= dp << x
        return (dp >> target) & 1 == 1

function canPartition(nums) {
    let total = 0;
    for (const x of nums) total += x;
    if (total % 2) return false;
    const target = total / 2;
    // BigInt as a bitset — bit i set means sum i is reachable.
    let dp = 1n;
    for (const x of nums) {
        dp |= dp << BigInt(x);
    }
    return ((dp >> BigInt(target)) & 1n) === 1n;
}

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        if (total % 2 != 0) return false;
        int target = total / 2;
        // BitSet as bitset — bit i set means sum i is reachable.
        java.util.BitSet dp = new java.util.BitSet(target + 1);
        dp.set(0);
        for (int x : nums) {
            // Shift dp left by x bits, then OR into dp.
            java.util.BitSet shifted = new java.util.BitSet(target + 1);
            for (int i = dp.previousSetBit(target); i >= 0; i = dp.previousSetBit(i - 1)) {
                if (i + x <= target) shifted.set(i + x);
            }
            dp.or(shifted);
        }
        return dp.get(target);
    }
}

function canPartition(nums: number[]): boolean {
    let total = 0;
    for (const x of nums) total += x;
    if (total % 2) return false;
    const target = total / 2;
    // BigInt as a bitset — bit i set means sum i is reachable.
    let dp = 1n;
    for (const x of nums) {
        dp |= dp << BigInt(x);
    }
    return ((dp >> BigInt(target)) & 1n) === 1n;
}