Problem Description

You are given an integer array nums. Your task is to determine if you can split this array into two subsets where both subsets have equal sums.

For example, if you have the array [1, 5, 11, 5], you can partition it into [1, 5, 5] and [11], where both subsets sum to 11. Therefore, the answer would be true.

However, if you have the array [1, 2, 3, 5], the total sum is 11 (which is odd), so it's impossible to split it into two equal-sum subsets. The answer would be false.

The problem asks you to return true if such a partition is possible, and false otherwise.

Key observations:

• If the total sum of the array is odd, it's impossible to partition it into two equal subsets
• If the total sum is even, the problem becomes: can we find a subset that sums to exactly half of the total sum?
• This is essentially a subset sum problem where the target is sum(nums) / 2

Intuition

The key insight is recognizing that if we can partition an array into two subsets with equal sums, then each subset must have a sum equal to exactly half of the total array sum. This immediately tells us that if the total sum is odd, partitioning is impossible.

When the total sum is even, we need to find if there's a subset that sums to target = total_sum / 2. If such a subset exists, the remaining elements will automatically form another subset with the same sum.

This transforms our problem into the classic "Subset Sum" problem: can we select some elements from the array that sum to a specific target?

To solve this, we can think about it step by step. For each element in the array, we have two choices: either include it in our subset or exclude it. This leads us to think about dynamic programming.

We can build up our solution by considering: "Can we achieve sum j using the first i elements?" For each element x at position i:

• If we don't include x, then achieving sum j depends on whether we could achieve sum j using the first i-1 elements
• If we include x, then achieving sum j depends on whether we could achieve sum j-x using the first i-1 elements (we need j-x from previous elements plus x to make j)

Starting from the base case where we can achieve sum 0 with 0 elements, we can build up a table that tells us whether each sum is achievable with each subset of elements, ultimately answering whether sum target is achievable using all available elements.

Solution Approach

We implement the solution using dynamic programming with a 2D boolean array.

First, we calculate the total sum of nums and check if it's even:

m, mod = divmod(sum(nums), 2)
if mod:
    return False

If the sum is odd (mod != 0), we return false immediately. Otherwise, our target sum is m = sum(nums) // 2.

Next, we create a 2D DP table f where f[i][j] represents whether we can achieve sum j using the first i numbers:

f = [[False] * (m + 1) for _ in range(n + 1)]

The table has dimensions (n+1) × (m+1) to handle the base case and all possible sums from 0 to m.

We initialize the base case:

f[0][0] = True

This means we can achieve sum 0 using 0 elements (by selecting nothing).

Now we fill the DP table iteratively. For each number x at position i (1-indexed) and each possible sum j from 0 to m:

for i, x in enumerate(nums, 1):
    for j in range(m + 1):
        f[i][j] = f[i - 1][j] or (j >= x and f[i - 1][j - x])

The state transition equation is:

• f[i][j] = f[i - 1][j] - we don't select the current number x, so we inherit the result from using the first i-1 numbers
• If j >= x, we can also try selecting x: f[i][j] = f[i][j] or f[i - 1][j - x] - we check if we could achieve sum j - x with the first i-1 numbers

The condition j >= x ensures we only try to include x when the target sum j is at least as large as x.

Finally, we return f[n][m], which tells us whether we can achieve sum m using all n numbers (though we don't have to use all of them - we just have them available for selection).

Example Walkthrough

Let's walk through the example nums = [1, 5, 11, 5] to illustrate the solution approach.

Step 1: Check if partition is possible

• Total sum = 1 + 5 + 11 + 5 = 22 (even)
• Target sum for each subset = 22 / 2 = 11
• Since the sum is even, we proceed with DP

Step 2: Initialize DP table We create a table f[i][j] where i represents "using first i numbers" and j represents "achieving sum j".

• Dimensions: 5 rows (0 to 4 numbers) × 12 columns (sums 0 to 11)
• Base case: f[0][0] = True (we can achieve sum 0 with 0 numbers)

Step 3: Fill the DP table iteratively

Processing nums[0] = 1 (i = 1):

• For each sum j from 0 to 11:
  • f[1][0] = f[0][0] = True (don't take 1)
  • f[1][1] = f[0][0] = True (take 1: 0 + 1 = 1)
  • f[1][2...11] = False (can't achieve these sums with just 1)

Processing nums[1] = 5 (i = 2):

• Notable updates:
  • f[2][0] = True (don't take anything)
  • f[2][1] = True (inherited from f[1][1])
  • f[2][5] = f[1][0] = True (take 5: 0 + 5 = 5)
  • f[2][6] = f[1][1] = True (take 5: 1 + 5 = 6)

Processing nums[2] = 11 (i = 3):

• Notable updates:
  • Previous sums remain achievable
  • f[3][11] = f[2][0] = True (take 11: 0 + 11 = 11) ✓

At this point, f[3][11] = True, meaning we can achieve sum 11 using the first 3 numbers. We could stop here, but let's complete the table.

Processing nums[3] = 5 (i = 4):

• f[4][11] remains True (inherited from f[3][11])

Step 4: Return result f[4][11] = True, confirming we can partition the array into two equal-sum subsets.

Indeed, we can form subset [1, 5, 5] with sum 11, leaving [11] with sum 11.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is half of the total sum of the array and n is the length of the array. The algorithm uses a 2D dynamic programming approach with a nested loop structure - the outer loop iterates through all n elements in the array, and the inner loop iterates through all possible sums from 0 to m. Each cell computation f[i][j] = f[i - 1][j] or (j >= x and f[i - 1][j - x]) takes O(1) time, resulting in an overall time complexity of O(m × n).

The space complexity is O(m × n). The algorithm creates a 2D boolean array f with dimensions (n + 1) × (m + 1) to store the dynamic programming states. Each cell in this array represents whether it's possible to achieve a sum of j using the first i elements from the input array. Since we're storing all intermediate results in this 2D table, the space requirement is proportional to O((n + 1) × (m + 1)), which simplifies to O(m × n).

Common Pitfalls

1. Space Complexity Optimization Overlooked

The current solution uses O(n × target) space with a 2D DP table. Since each row only depends on the previous row, we can optimize this to O(target) space using a 1D array.

Issue: Using unnecessary memory when dealing with large arrays or large sum values.

Solution: Use a 1D DP array and iterate backwards to avoid overwriting values we still need:

def canPartition(self, nums: List[int]) -> bool:
    total_sum = sum(nums)
    target, remainder = divmod(total_sum, 2)
  
    if remainder != 0:
        return False
  
    # Use 1D DP array instead of 2D
    dp = [False] * (target + 1)
    dp[0] = True
  
    for num in nums:
        # Iterate backwards to avoid using updated values
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
  
    return dp[target]

2. Integer Overflow in Other Languages

While Python handles large integers automatically, in languages like Java or C++, calculating sum(nums) could cause integer overflow for large arrays with large values.

Issue: Getting incorrect results due to overflow when calculating the total sum.

Solution: Use appropriate data types (like long in Java) or check for overflow conditions:

// Java example
long totalSum = 0;
for (int num : nums) {
    totalSum += num;
}

3. Early Termination Opportunities Missed

The current solution always processes all elements even when we've already found that we can achieve the target sum.

Issue: Wasting computation time when the answer could be determined earlier.

Solution: Add early termination checks:

def canPartition(self, nums: List[int]) -> bool:
    total_sum = sum(nums)
    target, remainder = divmod(total_sum, 2)
  
    if remainder != 0:
        return False
  
    # Early termination: if any single element equals target
    if target in nums:
        return True
  
    # Early termination: if largest element > target
    if max(nums) > target:
        return False
  
    dp = [False] * (target + 1)
    dp[0] = True
  
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
      
        # Early termination: check if target is achieved
        if dp[target]:
            return True
  
    return dp[target]

4. Not Handling Edge Cases

Failing to handle special cases like empty arrays or arrays with single elements.

Issue: Runtime errors or incorrect results for edge cases.

Solution: Add edge case checks at the beginning:

def canPartition(self, nums: List[int]) -> bool:
    # Edge cases
    if not nums or len(nums) < 2:
        return False
  
    total_sum = sum(nums)
    target, remainder = divmod(total_sum, 2)
  
    if remainder != 0:
        return False
  
    # Continue with DP solution...

5. Incorrect Index Mapping in 2D DP

When using 2D DP, confusion between 0-indexed arrays and 1-indexed DP table can lead to off-by-one errors.

Issue: Accessing nums[i] instead of nums[i-1] when i represents the DP table row (1-indexed).

Solution: Be consistent with indexing and add clear comments:

# Correct indexing
for i in range(1, n + 1):
    current_num = nums[i - 1]  # i is 1-indexed for DP, nums is 0-indexed
    for j in range(target + 1):
        dp[i][j] = dp[i - 1][j]
        if j >= current_num:
            dp[i][j] = dp[i][j] or dp[i - 1][j - current_num]