416. Partition Equal Subset Sum (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        s = sum(nums)
        if s % 2 == 1:
            return False
        n = s // 2
        arr = {0}
        for num in nums:
            tempArr = set()
            for val in arr:
                newVal = val + num
                if newVal == n:
                    return True
                if newVal < n:
                    tempArr.add(newVal)
            arr |= tempArr
        return False