0/1 Knapsack — Partition Equal Subset Sum

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;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for (int x : nums) {
            for (int s = target; s >= x; --s) dp[s] = dp[s] || dp[s - x];
            if (dp[target]) return true;
        }
        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
    dp := make([]bool, target+1)
    dp[0] = true
    for _, x := range nums {
        for s := target; s >= x; s-- {
            dp[s] = dp[s] || dp[s-x]
        }
        if dp[target] {
            return true
        }
    }
    return dp[target]
}

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for x in nums:
            for s in range(target, x - 1, -1):
                if dp[s - x]:
                    dp[s] = True
            if dp[target]:
                return True
        return dp[target]

function canPartition(nums) {
    let total = 0;
    for (const x of nums) total += x;
    if (total % 2) return false;
    const target = total / 2;
    const dp = new Uint8Array(target + 1);
    dp[0] = 1;
    for (const x of nums) {
        for (let s = target; s >= x; s--) {
            if (dp[s - x]) dp[s] = 1;
        }
        if (dp[target]) return true;
    }
    return dp[target] === 1;
}

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;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int x : nums) {
            for (int s = target; s >= x; s--) {
                if (dp[s - x]) dp[s] = true;
            }
            if (dp[target]) return true;
        }
        return dp[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;
    const dp: Uint8Array = new Uint8Array(target + 1);
    dp[0] = 1;
    for (const x of nums) {
        for (let s = target; s >= x; s--) {
            if (dp[s - x]) dp[s] = 1;
        }
        if (dp[target]) return true;
    }
    return dp[target] === 1;
}