Partition Equal Subset Sum — 0/1 Knapsack

Problem

Partition array into two subsets with equal sum. (Total must be even; find subset summing to total/2.)

Approach — 0/1 Knapsack Boolean DP

dp[j] = can we make sum j using elements seen so far. For each number, update backwards.

Time: O(n * sum) | Space: O(sum)

Solutions

Python — Bitset

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total=sum(nums)
        if total%2: return False
        target=total//2
        dp=1<<0
        for n in nums: dp|=dp<<n
        return bool(dp>>target&1)

Python — Boolean DP

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 n in nums:
            for j in range(target,n-1,-1):
                dp[j]|=dp[j-n]
        return dp[target]

C++

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 n:nums)
            for(int j=target;j>=n;j--) dp[j]=dp[j]||dp[j-n];
        return dp[target];
    }
};

Java

class Solution {
    public boolean canPartition(int[] nums){
        int total=0; for(int n:nums) total+=n;
        if(total%2!=0) return false;
        int t=total/2; boolean[] dp=new boolean[t+1]; dp[0]=true;
        for(int n:nums)
            for(int j=t;j>=n;j--) dp[j]=dp[j]||dp[j-n];
        return dp[t];
    }
}

Complexity

Time: O(n * sum/2) | Space: O(sum/2)

Key Takeaway

0/1 knapsack: loop amounts backwards (each item used at most once). Unbounded: loop forwards.