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]