Partition Equal Subset Sum

Problem Statement

Given an array of positive integers, can you split it into two subsets with equal sums? This medium-level DP riddle is like balancing a scale—find harmony in numbers!

Example

Input: nums = [1, 5, 11, 5]

Output: true (1+11 = 5+5 = 12)

Input: nums = [1, 2, 3, 5]

Output: false (no equal split)

Input: nums = [1, 2, 5]

Output: false (sum=8, no 4+4 split)

Code

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

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] |= dp[j - num]
    return dp[target]

# Example usage
print(can_partition([1, 5, 11, 5]))  # True
print(can_partition([1, 2, 3, 5]))  # False
            

function canPartition(nums) {
    let sum = nums.reduce((a, b) => a + b, 0);
    if (sum % 2 !== 0) return false;
    let target = sum / 2;
    let dp = new Array(target + 1).fill(false);
    dp[0] = true;
    for (let num of nums) {
        for (let j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

// Example usage
console.log(canPartition([1, 5, 11, 5]));  // True
console.log(canPartition([1, 2, 3, 5]));  // False
            

Explanation

• DP Insight: Find if a subset sums to half the total (0/1 knapsack variant).
• Steps: If sum is odd, fail. Use dp[j] = can we make sum j?
• Flow Example ([1,5,11,5]): target=12, dp[1]=T, dp[5]=T, dp[6]=T, dp[11]=T, dp[12]=T.
• Why It Works: Boolean array tracks all possible sums.

Note