416. Partition Equal Subset Sum – Leetcode Solutions

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.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # Calculate the total sum of the array
        total_sum = sum(nums)
        
        # If the total sum is odd, it's impossible to split into two equal subsets
        if total_sum % 2 != 0:
            return False
        
        # Target subset sum is half of the total sum
        target = total_sum // 2
        
        # DP array where dp[j] means whether a subset sum of j is possible
        dp = [False] * (target + 1)
        dp[0] = True  # Base case: a subset sum of 0 is always possible
        
        # Process each number in the array
        for num in nums:
            # Update the DP array from right to left
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]
        
        # The result is whether the target sum is achievable
        return dp[target]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // Step 1: Calculate the total sum of all elements in the array
        int totalSum = accumulate(nums.begin(), nums.end(), 0);

        // Step 2: If the total sum is odd, it's not possible to partition into two equal subsets
        if (totalSum % 2 != 0) {
            return false;
        }

        // Step 3: Define the target sum for each subset (half of totalSum)
        int target = totalSum / 2;

        // Step 4: Create a boolean DP array to track possible sums
        vector<bool> dp(target + 1, false);

        // Step 5: Initialize dp[0] to true because a sum of 0 is always possible
        dp[0] = true;

        // Step 6: Iterate through each number in the input array
        for (int num : nums) {
            // Step 7: Update the DP array in reverse to avoid overwriting
            for (int j = target; j >= num; --j) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        // Step 8: Return the result stored in dp[target]
        return dp[target];
    }
};

 function canPartition(nums) {
    // Step 1: Calculate the total sum of the array
    const totalSum = nums.reduce((sum, num) => sum + num, 0);

    // If the total sum is odd, it is impossible to split the array into two equal parts
    if (totalSum % 2 !== 0) {
        return false;
    }

    // Target sum for each subset is half of the total sum
    const target = totalSum / 2;

    // Step 2: Initialize a boolean DP array where dp[i] represents whether a subset sum of 'i' is possible
    const dp = new Array(target + 1).fill(false);
    dp[0] = true; // Base case: A subset sum of 0 is always possible (empty subset)

    // Step 3: Iterate through each number in the array
    for (let num of nums) {
        // Update the DP array in reverse to avoid overwriting values from the current iteration
        for (let j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    // Step 4: Check if a subset with the target sum is possible
    return dp[target];
}

class Solution {
    public boolean canPartition(int[] nums) {
        // Step 1: Calculate the total sum of the array
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        // Step 2: If the total sum is odd, it is not possible to partition the array
        if (totalSum % 2 != 0) {
            return false;
        }

        // Step 3: Determine the target sum for each subset (half of the total sum)
        int target = totalSum / 2;

        // Step 4: Use dynamic programming to determine if a subset with the target sum exists
        // dp[i] represents whether a sum of 'i' can be formed using elements in the array
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // Base case: a sum of 0 is always achievable (empty subset)

        // Step 5: Iterate through the numbers in the array
        for (int num : nums) {
            // Update the dp array from right to left
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        // Step 6: Check if the target sum is achievable
        return dp[target];
    }
}