Skip to content

416. Partition Equal Subset Sum

Array Dynamic Programming

Problem - Partition Equal Subset Sum

Medium

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # m, mod = divmod(sum(nums), 2)

        # # if the sum is odd it can't be split into two subsets
        # if mod:
        #     return False

        # n = len(nums)
        # dp = [[False] * (m + 1) for _ in range(n + 1)]
        # dp[0][0] = True

        # for i, num in enumerate(nums, 1):
        #     for j in range(m + 1):
        #         dp[i][j] = dp[i - 1][j] or (j >= num and dp[i - 1][j - num])

        # return dp[-1][-1]

        m, mod = divmod(sum(nums), 2)

        # if the sum is odd it can't be split into two subsets
        if mod:
            return False

        dp = [True] + [False] * m
        for num in nums:
            for j in range(m, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]
        return dp[-1]

Submission Stats:

  • Runtime: 622 ms (55.99%)
  • Memory: 18 MB (74.60%)