Partition Equal Subset Sum

Question

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or 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.

Solution

Intuition

By partition into 2 equals subset sums. It basically the same thing as the sum of all element in the array should be able to divide by 2

So as a result, if the sum of the array is odd, we can just return False.

Now the question is if the sum of the array is even, how do we know that we can divide into 2 group.

We know that we can divide into 2 group if we can form a half sum using elements in the array.

For example, consider the array [1,5,11,5]. The sum of everything is 22.

If using any elements in the array, and somehow we can form 22 / 2 = 11, that means the other rest of the group should also be 11.

As a result, we can generate all the possible sum from the group and see if we can form a half sum.

Consider [1,5,11,5]. We could go like this:

With 1, we can generate [1] as the sum.
With 1, 5, we can generate [1, 5, 6] as the sum. We simply use 5 and add to all the current sum we found so far.
With 1, 5, 11, we can genereate [1, 5, 6, 12, 16, 17, 11]. We use 11 to add to all the current sum we found so far.

Since now we have 11 (which is our target of 22 / 2), we say that we can form a half sum and return True

Implementation

class App:
    def canPartition(self, nums: List[int]) -> bool:
        totalSum = sum(nums)
        if totalSum % 2 != 0: return False
        
        sumSet = set()
        
        target = totalSum / 2
        
        for num in nums:
            sumSetList = list(sumSet)

            for i in range(0, len(sumSetList)):
                sumSet.add(sumSetList[i] + num)
            
            sumSet.add(num)
            
            if target in sumSet: 
                return True
                
        return False

Time complexity: $O(n \times s)$

$n$ is the number of element
$s$ is the number of unique sum in sumSet

Space complexity: $O(n \times s)$