416 分割等和子集

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

注意:

1. 每个数组中的元素不会超过 100
2. 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

解法

• 动态规划

首先判断数组的和是否为偶数，为偶数则可分成两部分，为奇数返回False。

那么该问题转化为，数组中的某些元素之和是否等于 sum(nums)//2。

构建状态方程：

dp[i][j] 表示前i个数是否存在某些元素之和等于j
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]] 取第i个元素或者不取第i个元素

代码如下：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums)%2==1:
            return False
        else:
            target = sum(nums)//2
        dp = [[False for _ in range(target+1)] for _ in range(len(nums)+1)]
        dp[0][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] or dp[i-1][j-nums[i-1]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]