416. Partition Equal Subset Sum

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """

        if sum(nums)%2==1:
            return False
        
        target=sum(nums)//2
        dp=set()

        if target in nums:
            return True
        
        dp.add(0)
        for i in range(len(nums)-1,-1,-1):
            newDP=set()
            for t in dp:
                if (t+nums[i]==target):
                    return True
                newDP.add(t+nums[i])
                newDP.add(t)
            dp=newDP
        if target in dp:
            return True
        else:
            return False