Leetcode 416 Solution

This article provides solution to leetcode question 416 (partition-equal-subset-sum)
Categories:
Tags:
Access this page by simply typing in "lcs 416" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)

        if s % 2 == 1:
            return False

        target = s // 2
        dp = [0] * (target + 1)
        dp[0] = 1

        for num in nums:
            i = target

            while i >= 0:
                if dp[i] == 1 and num + i <= target:
                    dp[num + i] = 1
                i -= 1

        return dp[target]