Partition Equal Subset Sum Interview Question for Apple

# Partition Equal Subset Sum

## Problem Description

Given an integer array `nums`, determine whether 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 Approach (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. This can be achieved using recursion or bit manipulation. However, this approach has an exponential time complexity, making it inefficient for larger input arrays.

```python
def canPartition_brute_force(nums):
    n = len(nums)
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False
    
    target_sum = total_sum // 2

    def find_subset(index, current_sum):
        if current_sum == target_sum:
            return True
        if index >= n or current_sum > target_sum:
            return False

        # Include the current number or exclude it
        return find_subset(index + 1, current_sum + nums[index]) or find_subset(index + 1, current_sum)

    return find_subset(0, 0)

Optimal Approach (Dynamic Programming)

A more efficient approach uses dynamic programming. The core idea is to determine whether a subset exists that sums up to half of the total sum of the array. If the total sum is odd, a partition is impossible, so we can return false immediately. Otherwise, we create a DP table where dp[i] represents whether a subset with a sum of i can be formed using elements from the array.

def canPartition(nums):
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False
    
    target_sum = total_sum // 2
    n = len(nums)
    
    dp = [False] * (target_sum + 1)
    dp[0] = True
    
    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]

Big(O) Run-time Analysis

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

The brute force approach has a time complexity of O(2^n) because it explores all possible subsets of the input array.

Big(O) Space Usage Analysis

The dynamic programming approach uses O(target_sum) space for the DP table. This table stores boolean values indicating whether a particular sum can be achieved.

The brute force approach uses O(n) space in the worst case due to the recursion depth.

Edge Cases

Empty Array: If the input array is empty, it should return false because there are no elements to form two subsets.
Array with a Single Element: If the array contains only one element, it should return false because it is impossible to divide it into two subsets.
Array with Negative Numbers: If the array contains negative numbers, the problem becomes more complex. The standard dynamic programming approach needs to be modified to handle negative sums. The target_sum also needs to be adjusted accordingly.
Large Numbers: If the numbers in the array are very large, the target_sum can become large as well, which may lead to memory issues with the DP table. It is important to check for potential overflow issues.
Total Sum is Odd: As handled in the code, if the sum of all numbers in the array is odd, there's no way to divide the array into two subsets with equal sums, thus we should return false immediately.