刷题记录：416. 分割等和子集

416. 分割等和子集

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

        if target != int(target):
            return False
        n = len(nums)
        target = int(target)
        
        dp = [[False]*(target + 1) for _ in range(n + 1)]

        for i in range(n+1):
            dp[i][0] = True
        
        for i in range(1,n+1):
            for j in range(1,target+1):
                if j - nums[i-1] >= 0:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j - nums[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        
        return dp[-1][-1]