416.py

# leetcode 416 分割等和子集


# 单数组版本
class Solution:
    def canPartition(self, nums: List[int]) -> bool:

        _sum = sum(nums)

        if _sum % 2 != 0:
            return False

        target = _sum // 2

        dp = [0 for _ in range(target + 1)]

        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = max(dp[j], dp[j - num] + num)

        return dp[-1] == target


# 二维数组版本

class Solution:
    def canPartition(self, nums: List[int]) -> bool:

        _sum = sum(nums)

        if _sum % 2 != 0:
            return False

        target = _sum // 2

        dp = [[False] * (target + 1) for _ in range(len(nums) + 1)]

        for i in range(len(nums) + 1):
            dp[i][0] = True

        for i in range(1, len(nums) + 1):
            for j in range(1, target + 1):

                if j < nums[i - 1]:
                    dp[i][j] = dp[i - 1][j]

                else:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]

        return dp[-1][-1]