Partition Equal Subset Sum Interview Question for Amazon

## Partition Equal Subset Sum

This problem asks whether we can divide an array `nums` into two subsets such that the sum of elements in both subsets is equal. Let's explore different approaches to solve this problem, starting with a naive solution and then moving towards an optimal dynamic programming solution.

### 1. Naive Approach (Brute Force)

The most straightforward approach is to generate all possible subsets of `nums` and check if any two subsets have equal sums. This can be done using recursion.

```python
def canPartition_bruteforce(nums):
    n = len(nums)

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

        # Include the current element or exclude it
        return subset_sum(index + 1, current_sum + nums[index], target_sum) or \
               subset_sum(index + 1, current_sum, target_sum)

    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False  # If the total sum is odd, it can't be partitioned into two equal subsets.

    target_sum = total_sum // 2
    return subset_sum(0, 0, target_sum)

# Example usage
nums = [1, 5, 11, 5]
print(canPartition_bruteforce(nums))  # Output: True

Explanation:

The subset_sum function recursively checks if there's a subset with a specific sum.
We either include the current element or exclude it in each recursive call.
If the total sum is odd, we immediately return False because it's impossible to partition it into two equal subsets.

However, this approach is very inefficient due to its exponential time complexity.

2. Optimal Solution (Dynamic Programming)

A more efficient approach is to use dynamic programming. We can create a DP table dp where dp[i] is True if a subset with sum i can be formed using the elements from nums, and False otherwise.

def canPartition(nums):
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False  # If the total sum is odd, it can't be partitioned into two equal subsets.

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

    # dp[i] is True if a subset with sum i can be formed using elements from nums.
    dp = [False] * (target_sum + 1)
    dp[0] = True  # An empty set has sum 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
nums = [1, 5, 11, 5]
print(canPartition(nums))  # Output: True

nums = [1, 2, 3, 5]
print(canPartition(nums))  # Output: False

Explanation:

We first calculate the total sum of the array. If it's odd, we return False.
We create a DP table dp of size target_sum + 1.
dp[0] is initialized to True because a subset with sum 0 can always be formed (an empty set).
We iterate through each number in nums and update the DP table. For each number, we iterate from target_sum down to num and check if dp[i - num] is True. If it is, it means that we can form a subset with sum i by including the current number.

3. Big(O) Time Complexity Analysis

Brute Force: O(2^n), where n is the number of elements in nums. This is because we generate all possible subsets.
Dynamic Programming: O(n * target_sum), where n is the number of elements in nums and target_sum is half of the total sum. The nested loops iterate through each element and each possible sum.

4. Big(O) Space Complexity Analysis

Brute Force: O(n) due to the recursive call stack.
Dynamic Programming: O(target_sum) because we use a DP table of size target_sum + 1.

5. Edge Cases

Empty Array: If the input array nums is empty, the problem is not well-defined. However, for the purpose of this problem, we can assume an empty array cannot be partitioned into two equal subsets, so return False.
Array with a Single Element: If the array has only one element, it can't be partitioned into two equal subsets, so return False.
Large Sum: If the total sum of the array is very large, the DP table can become very large, leading to memory issues. In practice, the problem constraints limit the size of the array and the value of each element, so this is usually not a concern.
Negative Numbers: The problem statement specifies that all numbers are positive. If negative numbers were allowed, the problem would become more complex and require additional considerations in the dynamic programming approach. We would need to shift the indices to handle negative sums.

def canPartition_edge_cases(nums):
    if not nums:
        return False  # Empty array
    
    if len(nums) == 1:
        return False  # Single element array
    
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False  # Odd total sum
    
    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]