Partition Equal Subset Sum

Given an integer array nums, determine if it is possible to partition the array into two subsets such that the sum of the elements in both subsets is equal. Return true if such a partition is possible, and 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.

# Partition Equal Subset Sum

## Problem Description

Given an integer array `nums`, determine if it is possible to partition the array into two subsets such that the sum of the elements in both subsets is equal. Return `true` if such a partition is possible, and `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.

## Naive Solution (Brute Force)

The most straightforward approach is to generate all possible subsets of the given array and check if any two subsets have equal sums. However, this approach has exponential time complexity, making it impractical for larger arrays.

## Optimal Solution (Dynamic Programming)

A more efficient solution utilizes dynamic programming. The core idea is to determine if a subset exists that sums up to half the total sum of the array. If the total sum is odd, it's impossible to partition the array into two equal sum subsets, so we return `false`. Otherwise, we use a dynamic programming table to track whether a subset with a particular sum can be formed using the elements encountered so far.

```python
def canPartition(nums):
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False

    target_sum = total_sum // 2
    n = len(nums)

    # dp[i] is True if a subset of nums[0...j] can sum to i
    dp = [False] * (target_sum + 1)
    dp[0] = True  # An empty set sums to 0

    for num in nums:
        for i in range(target_sum, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]

    return dp[target_sum]

Example Usage

nums1 = [1, 5, 11, 5]
print(f"Can partition {nums1}: {canPartition(nums1)}")  # Output: True

nums2 = [1, 2, 3, 5]
print(f"Can partition {nums2}: {canPartition(nums2)}")  # Output: False

Big(O) Runtime Analysis

The time complexity of the dynamic programming solution is O(n * target_sum), where n is the number of elements in the input array, and target_sum is half of the total sum of the elements. The nested loop iterates through each element and each possible sum value up to the target sum.

Big(O) Space Usage Analysis

The space complexity of this solution is O(target_sum), as we use a one-dimensional dynamic programming table (dp) of size target_sum + 1 to store the intermediate results.

Edge Cases and Considerations

1. Empty Array: If the input array is empty, it can be considered as partitionable (vacuously true). However, the problem statement specifies 1 <= nums.length <= 200, so this isn't strictly a valid edge case.
2. Array with Single Element: If the array has only one element, it cannot be partitioned into two equal sum subsets, so the function should return false.
3. Large Sum: The problem statement says that each number is between 1 and 100 and the array has at most 200 elements. In the worst case scenario where every element is 100 the target sum will be 200 * 100 / 2 = 10,000. The space usage is therefore O(10,000) = O(1). Therefore the space complexity of O(target_sum) is not an issue based on the problem constraints.
4. Negative Numbers: The problem statement specifies positive integers only. If negative numbers were allowed, the dynamic programming approach would need to be modified to handle negative sums.