Partition Equal Subset Sum Interview Question for Meta

# Partition Equal Subset Sum

## Problem Description

Given an integer array `nums`, determine if it's possible to partition the array into two subsets such that the sum of 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 the same sum. This can be done recursively.

```python
def canPartition_bruteforce(nums):
    def get_all_subsets(index, current_subset, all_subsets):
        if index == len(nums):
            all_subsets.append(current_subset.copy())
            return
        
        # Include the current number
        current_subset.append(nums[index])
        get_all_subsets(index + 1, current_subset, all_subsets)
        current_subset.pop()
        
        # Exclude the current number
        get_all_subsets(index + 1, current_subset, all_subsets)
    
    all_subsets = []
    get_all_subsets(0, [], all_subsets)
    
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False
    
    target_sum = total_sum // 2
    
    for subset in all_subsets:
        if sum(subset) == target_sum:
            return True
    
    return False

This approach has exponential time complexity because it generates all possible subsets. It's highly inefficient and not suitable for larger input sizes.

Optimal Solution (Dynamic Programming)

A more efficient approach is to use dynamic programming. The problem can be reframed as a subset sum problem: can we find a subset of nums that sums to target_sum = sum(nums) / 2?

Calculate the total sum: If the total sum of the array is odd, it's impossible to partition the array into two equal sum subsets. Return false.
Determine the target sum: target_sum = total_sum / 2.
Create a DP table: dp[i][j] is true if a subset of the first i elements can sum to j, and false otherwise.
Initialize the DP table:
- dp[i][0] = true for all i (an empty subset can always sum to 0).
- dp[0][j] = false for all j > 0 (without any elements, we cannot sum to a value greater than 0).
Fill the DP table:
- For each element nums[i-1] and each sum j:
  - If nums[i-1] > j, then dp[i][j] = dp[i-1][j] (we can't include the current element because it's too large).
  - Otherwise, dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i-1]] (we can either exclude the current element or include it if including it allows us to reach the sum j).
Return the result: dp[n][target_sum] (whether a subset of all n elements can sum to target_sum).

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) for _ in range(n + 1)]

    # Initialization
    for i in range(n + 1):
        dp[i][0] = True

    # Fill the DP table
    for i in range(1, n + 1):
        for j in range(1, target_sum + 1):
            if nums[i - 1] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]

    return dp[n][target_sum]

Big(O) Time Complexity Analysis

The dynamic programming solution has a time complexity of 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. This is because we iterate through the dp table which has dimensions (n+1) x (target_sum+1). The bruteforce approach has O(2^n) since we must consider all subsets.

Big(O) Space Complexity Analysis

The dynamic programming solution has a space complexity of O(n * target_sum) due to the dp table. We use a 2D boolean array to store intermediate results. We could potentially optimize this to O(target_sum) by using only one row, but for clarity I have kept it as O(n*target_sum).

Edge Cases

Empty Array: If the input array is empty, it can be considered as partitioned into two empty subsets, so return true.
Single Element Array: If the array has only one element, it cannot be partitioned, so return false.
Array with Zero Sum: If the array's sum is zero, then two empty subsets will both have zero sum, so return true.
Large Input Values: If the values in the array are very large, the target_sum can become very large, which increases the time and space complexity. This is a limitation of this approach.

Alternative DP approach (Space optimized)

We can optimize the space complexity of the DP solution from O(n*target_sum) to O(target_sum) by using only one row in the DP table. This is because to calculate the current row, we only need information from the previous row. This space optimization comes with the requirement of iterating backwards through the target_sum values. This is required because we want to use the dp[j] value from the previous iteration, and if we iterate forwards, we'd be using the dp[j] value from the current iteration.

def canPartition_optimized(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 j in range(target_sum, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]

    return dp[target_sum]

The time complexity remains O(n * target_sum), while the space complexity is reduced to O(target_sum).