Partition Equal Subset Sum

 #Approach 1: Keeping Track of all sums possible so far
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        tot = sum(nums)
        if tot&1 == 1:
            return False
        tar = tot//2

        sums = set([0]) #use set to prevent duplicate sums
        for i in nums:
            for j in sums.copy():
                if i+j == tar:
                     return True
                if i+j < tar:
                    sums.add(i+j)

        return False

#Approach 2: 2-D dp
'''
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        tot = sum(nums)

        if tot&1 == 1:
            return False

        tar = tot//2
        dp = [[True]+[False]*(tar)]

        for i in nums:
            dp.append(dp[-1][:])
            for j in range(i, tar+1):
                dp[-1][j] = dp[-1][j] or dp[-2][j-i]
            if dp[-1][-1] == True:
                return True

        return False
'''

#Approach 3: optmized space dp
'''
class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        tot = sum(nums)

        if tot&1 == 1:
            return False

        tar = tot//2
        dp = [True]+[False]*(tar)

        for i in nums:
            dp_prev = dp[:]
            for j in range(i, tar+1):
                dp[j] = dp_prev[j] or dp_prev[j-i]
            if dp[-1] == True:
                return True

        return False
'''