416. 分割等和子集 · Algorithm Lab

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入： nums = 1,5,11,5输出： true 解释： 数组可以分割成 1, 5, 5 和 11 。

示例 2：

输入： nums = 1,2,3,5输出： false 解释： 数组不能分割成两个元素和相等的子集。

提示：

1 <= nums.length <= 200
1 <= nums[i] <= 100

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


class Solution(object):
    def canPartition(self, nums):
        # 总数除二，变成能否取得等值序列
        total_sum = sum(nums)
        if total_sum % 2 != 0:
            return False
        target = total_sum // 2

        if target < max(nums):  # 单个元素超过一半
            return False
        
        dp = [False] * (target + 1)
        dp[0] = True # 和为0一定存在（空集）
        for num in nums:
            for j in range(target, num - 1, -1):  # 逆序遍历
                # 如果j-num能凑出，或者j本身已经凑出 
                dp[j] = dp[j] or dp[j - num] 

        return dp[target]
        """
        :type nums: List[int]
        :rtype: bool
        """