LC 416分割等和子集Partition Equal Subset Sum　中等

判断数组能否划分成两个子集，使两个子集的元素和相等。

思路 0-1 背包：目标和为 sum/2，dp[j] 表示和 j 可达，j 从大到小倒序转移防重复。时间 O(n·sum)。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s % 2:
            return False
        t = s // 2
        dp = [True] + [False] * t
        for x in nums:
            for j in range(t, x - 1, -1):
                dp[j] = dp[j] or dp[j - x]
        return dp[t]