Partition Equal Subset Sum

Problem

https://leetcode.com/problems/partition-equal-subset-sum/

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.

Constraints:

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 100

Pattern

Array, Dynamic Programming

Approaches

Dynamic Programming

Code

def canPartition(nums: list[int]) -> bool:
    S = sum(nums)
    if S % 2 != 0:
        return False

    target = S // 2

    sums_so_far = set([0])
    for num in nums:
        next_sums_so_far = set()
        for s in sums_so_far:
            if num + s == target:
                return True
            if num + s < target:
                next_sums_so_far.add(s + num)

            next_sums_so_far.add(s)

        sums_so_far = next_sums_so_far

    return False

Test

>>> from partition_equal_subset_sum__dynamic_programming import canPartition
>>> canPartition([1, 5, 11, 5])
True
>>> canPartition([1, 2, 3, 5])
False

partition_equal_subset_sum__dynamic_programming.canPartition(nums: list[int]) → bool