How to Solve Partition Equal Subset Sum

Partition Equal Subset Sum Introduction

The Partition Equal Subset Sum asks us to determine if the given array can be split such that the two partition sums are equal. This problem requires careful consideration and checks such as checking if the sum is divisible by two and sorting the array so that we can keep a running current sum until we equal the target sum.

Partition Equal Subset Sum Problem

Given an array of positive numbers, determine if the array can be split such that the two partition sums are equal.

Example Inputs and Outputs

Example 1

Input: nums = [1,5,11,5]

Output: True

Example 2

Input: nums = [1,2,3,5]

Output: False

Partition Equal Subset Sum Solutions

We can solve this problem using the dynamic programming approach. First, we calculate the total sum of the array and check if it is divisible by 2. If not, it is impossible to partition the array equally, so we return false. Next, we set the target sum as half of the total sum and sort the array in ascending order. We initialize a set called sums with an initial value of 0, representing an empty subset. We iterate through each number in the array and for each number, we create a new set called newSums to store the updated sums.

For each sum in the sums set, we add the current number to it and check if the new sum is equal to the target sum. If it is, we have found a valid partition, so we return true. If the new sum is less than the target sum, we add it to the newSums set. After iterating through all numbers, we update the sums set with the contents of the newSums set. If we cannot find a valid partition after iterating through all numbers, we return false. Our approach considers all possible combinations of numbers to determine if a valid partition exists.

Python Code

def canPartition(nums):
    total_sum = sum(nums)  # Calculate the total sum of the array

if total_sum % 2 != 0:  # If the sum is not divisible by 2, return False
        return False

target_sum = total_sum // 2  # Set the target sum as half of the total sum

nums.sort()  # Sort the array in ascending order

sums = set([0])  # Initialize a set to store the unique sums, starting with 0

for num in nums:
        if num > target_sum:  # If the current number is greater than the target sum, break the loop
            break

new_sums = set()  # Create a new set to store updated sums

for val in sums:
            new_sum = val + num

if new_sum == target_sum:  # If the new sum is equal to the target sum, return True
                return True
            elif new_sum < target_sum:  # If the new sum is less than the target sum, add it to the new_sums set
                new_sums.add(new_sum)

sums.update(new_sums)  # Update the sums set with the new_sums set

return False  # If a valid partition is not found, return False

Time/Space Complexity Analysis

• Time Complexity: O(n * sum), where n is the length of the input array. This is because for each number in the array, we iterate over the current set of sums, which has a maximum size of sum. Therefore, the overall time complexity is proportional to the number of iterations performed, which depends on the size of the array and the sum.
• Space Complexity: O(sum), as we use sets to store the unique sums.