Code Implementation

class Solution:
    def canPartition(self, nums):
        total = sum(nums)
        # If total sum is odd, cannot partition equally
        if total % 2 != 0:
            return False
        target = total // 2
        dp = set([0])
        for num in nums:
            next_dp = set(dp)
            for t in dp:
                if t + num == target:
                    return True
                if t + num <= target:
                    next_dp.add(t + num)
            dp = next_dp
        return target in dp
      

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        if (total % 2 != 0) return false;
        int target = total / 2;
        unordered_set<int> dp = {0};
        for (int num : nums) {
            unordered_set<int> next_dp(dp);
            for (int t : dp) {
                if (t + num == target) return true;
                if (t + num <= target) next_dp.insert(t + num);
            }
            dp = next_dp;
        }
        return dp.count(target) > 0;
    }
};
      

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int n : nums) total += n;
        if (total % 2 != 0) return false;
        int target = total / 2;
        HashSet<Integer> dp = new HashSet<>();
        dp.add(0);
        for (int num : nums) {
            HashSet<Integer> nextDp = new HashSet<>(dp);
            for (int t : dp) {
                if (t + num == target) return true;
                if (t + num <= target) nextDp.add(t + num);
            }
            dp = nextDp;
        }
        return dp.contains(target);
    }
}
      

var canPartition = function(nums) {
    let total = nums.reduce((a, b) => a + b, 0);
    if (total % 2 !== 0) return false;
    let target = total / 2;
    let dp = new Set([0]);
    for (let num of nums) {
        let nextDp = new Set(dp);
        for (let t of dp) {
            if (t + num === target) return true;
            if (t + num <= target) nextDp.add(t + num);
        }
        dp = nextDp;
    }
    return dp.has(target);
};
      

Problem Description

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

• You may not reuse any element from nums in both subsets.
• Each element must be used in exactly one subset.
• Return true if such a partition exists, otherwise false.

Constraints:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100
• There is at most one valid solution for each input.

Thought Process

The heart of the problem is deciding whether the array can be split into two groups with equal sums. At first glance, this seems related to finding all possible subsets and checking their sums, but that would be very inefficient for larger arrays.

If the total sum of the array is odd, it's immediately impossible—two equal integers can't sum to an odd number. If it's even, we need to determine whether any subset sums exactly to half the total (the other subset will automatically sum to the other half).

This leads to the classic "Subset Sum" problem: can we pick a subset of numbers from nums that adds up to a target (here, half the total)? Brute-forcing all subset combinations is exponential, so we look for optimizations, such as dynamic programming, to efficiently track which sums are possible as we process each number.

Solution Approach

We use a dynamic programming approach to solve the subset sum problem efficiently.

1. Check for Impossibility: If the sum of all elements is odd, return false immediately.
2. Target Calculation: Compute target = total_sum / 2. Our goal is to find a subset that sums to target.
3. DP Initialization: Use a set or boolean array to keep track of all possible subset sums as we iterate through the numbers. Start with 0 as the only achievable sum.
4. Iterate Through Numbers: For each number in nums:
   • For each sum we've previously been able to make, record that we can now also make sum + num (if it's not above target).
   • If at any point we can make target, return true early.
5. Final Check: After processing all numbers, if target is in the set of achievable sums, return true; otherwise, return false.

We use a set for possible sums because lookups and insertions are fast (O(1) average), and it avoids duplicates as we expand the set with each new number.

Example Walkthrough

Consider nums = [1, 5, 11, 5].

• Total sum: 1 + 5 + 11 + 5 = 22, which is even.
• Target: 22 / 2 = 11.
• DP Set Initialization: {0}
• Process 1:
  • From 0, can now make 1. Set: {0, 1}
• Process 5:
  • From 0, can make 5. From 1, can make 6. Set: {0, 1, 5, 6}
• Process 11:
  • From 0, can make 11 (match!), from 1 can make 12 (skip, over target), etc.
  • We find 11 in our set, so we return true.

The process stops as soon as we reach the target sum, confirming that a valid partition exists.

Time and Space Complexity

• Brute-Force Approach:
  • Time: O(2^n) — Every subset is considered.
  • Space: O(n) — Call stack or subset storage.
• Optimized DP Approach:
  • Time: O(n * target) — For each of n numbers, we may try up to target sums.
  • Space: O(target) — We only need to store possible sums up to target.

The optimized approach is much more efficient and feasible for the given constraints.

Summary

The Partition Equal Subset Sum problem boils down to determining if a subset of the array sums to exactly half the total. By using dynamic programming to efficiently track achievable sums as we process each number, we avoid the exponential blowup of brute-force solutions. The key insight is that if the total sum is odd, partitioning is impossible; otherwise, we check for the existence of a subset with sum equal to half the total. This approach is both elegant and practical for moderate input sizes.