416. Partition Equal Subset Sum

Problem Description

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Python Solution

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        
        # If total sum is odd, we can't partition into equal subsets
        if total_sum % 2 != 0:
            return False
        
        target = total_sum // 2
        dp = set([0])
        
        # For each number, check if we can make any new sums
        for num in nums:
            # We need to create a new set to avoid modifying while iterating
            next_dp = dp.copy()
            for curr_sum in dp:
                next_sum = curr_sum + num
                if next_sum == target:
                    return True
                if next_sum < target:
                    next_dp.add(next_sum)
            dp = next_dp
        
        return False

Java Solution

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        // If total sum is odd, we can't partition into equal subsets
        if (totalSum % 2 != 0) {
            return false;
        }
        
        int target = totalSum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        
        // For each number, check if we can make any new sums
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        
        return dp[target];
    }
}

C++ Solution

class Solution {
public:
    bool canPartition(vector& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        
        // If total sum is odd, we can't partition into equal subsets
        if (totalSum % 2 != 0) {
            return false;
        }
        
        int target = totalSum / 2;
        vector dp(target + 1, false);
        dp[0] = true;
        
        // For each number, check if we can make any new sums
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        
        return dp[target];
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function(nums) {
    const totalSum = nums.reduce((a, b) => a + b, 0);
    
    // If total sum is odd, we can't partition into equal subsets
    if (totalSum % 2 !== 0) {
        return false;
    }
    
    const target = totalSum / 2;
    const dp = new Set([0]);
    
    // For each number, check if we can make any new sums
    for (const num of nums) {
        const nextDp = new Set(dp);
        for (const currSum of dp) {
            const nextSum = currSum + num;
            if (nextSum === target) {
                return true;
            }
            if (nextSum < target) {
                nextDp.add(nextSum);
            }
        }
        dp = nextDp;
    }
    
    return false;
};

C# Solution

public class Solution {
    public bool CanPartition(int[] nums) {
        int totalSum = nums.Sum();
        
        // If total sum is odd, we can't partition into equal subsets
        if (totalSum % 2 != 0) {
            return false;
        }
        
        int target = totalSum / 2;
        bool[] dp = new bool[target + 1];
        dp[0] = true;
        
        // For each number, check if we can make any new sums
        foreach (int num in nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        
        return dp[target];
    }
}