416. Partition Equal Subset Sum

Description

Given a non-empty array of positive integers nums, determine if it can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Intuition

The problem can be reduced to finding if there exists a subset of nums that sums up to sum / 2, where sum is the total sum of the elements in nums. If the total sum is odd, it is impossible to partition the array into two equal subsets.

Approach

1. Calculate the total sum of the elements in nums.
2. If the total sum is odd, return false as it is impossible to partition the array into two equal subsets.
3. Set the target sum to be sum / 2.
4. Use dynamic programming to determine if there exists a subset with sum equal to the target sum. - Create a boolean array dp where dp[i] represents whether a subset with sum i can be formed using the elements in nums. - Initialize dp[0] to true because a subset with sum 0 is always possible (the empty subset). - For each number in nums, update the dp array from right to left to ensure that each number is only used once.
5. Return the value of dp[target], which indicates whether a subset with the target sum exists.

Complexity

Time Complexity:

O(n * sum/2), where n is the length of nums and sum/2 is the target sum.

Space Complexity:

O(sum/2) for the dp array.

Code

C++

class Solution {
public:
    bool canPartition(vector& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        
        if (sum % 2 != 0) {
            return false;
        }
        
        int half = sum / 2;
        vector dp(half + 1, false);
        dp[0] = true;
        
        for (int num : nums) {
            for (int i = half; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[half];
    }
};

Python

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total_sum = sum(nums)
        
        # If the total sum is odd, we can't split it into two equal subsets
        if total_sum % 2 != 0:
            return False
        
        target = total_sum // 2
        dp = [False] * (target + 1)
        dp[0] = True
        
        for num in nums:
            for i in range(target, num - 1, -1):
                dp[i] = dp[i] or dp[i - num]
        
        return dp[target]

Java

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();

        if (sum % 2 != 0) {
            return false;
        }

        int half = sum / 2;
        boolean[] dp = new boolean[half + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int i = half; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[half];
    }
}

JavaScript

var canPartition = function(nums) {
    var sum = nums.reduce((a, b) => a + b, 0);
    
    if (sum % 2 !== 0) {
        return false;
    }
    var half = sum / 2;
    var dp = [];
    dp[0] = true;
    for (var index = 0; index < nums.length; ++ index) {
        var num = nums[index];
        for (var i = half; i >= num; -- i) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[half] || false;
};