➕416. Partition Equal Subset Sum

Medium | Grind 75 | February 26th Sunday, 2023

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.

Constraints:

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 100

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

1. Calculate the sum of the nums list.

   1. if the sum is odd, return False since we can't split an odd number into two equal integer parts.

   2. Otherwise, continue to step 2

2. Initialize a DP, an array of size sum(nums)//2 (HALF) to hold boolean values indicating whether the particular number indicated by the array index can be formed by summing numbers from the nums list. Initialize DP[0] to True since the value of zero can always be formed by not adding anything from the nums list.

3. Iterate through the numbers in the nums list.

   1. For every number in the list, iterate from HALF to the current number - 1 to check if the current number can form any values from HALF to the current number-1. We check only until the current number - 1 because a number cannot sum to a value smaller than itself.

   2. During each iteration(HALF -> current number - 1), update DP of the current index as DP[current index - current number] or DP[current index].

      1. DP[current index - current number] takes care of cases where previous numbers from the nums list summed with the current number can form the current value. Additionally, it takes care of cases where the index and the current number are the same.

      2. DP[index] ensures the value of DP[index] remains true if it was previously true and DP[current index - current number] is false

4. Return the value of DP[HALF], which indicates whether a subset of numbers in the nums list can sum up to half of the total sum.

class Solution:
    def canPartition(self, nums: List[int]) -> bool: 
        total = sum(nums)
        # cannot split an odd integer number into equal half
        if total % 2: return False

        half = total//2

        # dp to see what numbers can be summed to using integers in nums list 
        dp = [False for i in range(half+1)]
        dp[0] = True
        
        for number in nums: 
            for i in range(half, number-1, -1): 
                dp[i] = dp[i-number] or dp[i]
        
        return dp[half]
          

TIME AND SPACE COMPLEXITY

TIME: O(n * m) where n is the length of the nums list and m is half of the sum of the nums list.

SPACE: O(m) where m is half of the sum of the nums list. This is the size of our DP