题目

难度：★★★☆☆
类型：数组
方法：动态规划

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

注意:

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

示例

示例 1:

输入: [1, 5, 11, 5]

输出: true

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

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

解答

这道题是典型的0-1背包问题的一个变种。有大佬对此有深入的分析。零一背包问题的大致需求是，在给定的数组中选取一些元素，使得这些元素的和等于目标值。对于当前的问题，目标值即为数组中所有元素和的一半，这里我们定义为target=sum(nums)//2。

首先注意特殊情况的排除，即当输入为空或者输入数组的和为奇数的情况。

剩下的，我们使用动态规划来解决这个问题。

定义一个布尔类型的二维数组dp，数组的维度为(len(nums), target+1)，dp[i][j]的含义为数组nums[0:i+1]中是否存在一些元素，使得它们的和为j，这里target+1的原因是需要覆盖从0到target的所有正整数。

初始情况：数组中所有元素初始化为False。dp[0]是一个长度为target+1的数组，表示nums[:1]数组中子数组的和是否可以组成j（0<=j<target），而这个数组中只包含一个元素，其和能构成的就是nums[0]，因此将dp[0][nums[0]]填充为True。

状态转移方程。逐行逐列遍历dp数组，如何判断nums[0:i+1]中是否有子数组和是j?我们有以下几个依据：

1. 如果nums[0:i]中有子数组和为j（也就是dp[i-1][j]的值为True），则nums[0:i+1]中一定有子数组和为j，多了一个元素而已；

2. 如果当前新增的元素nums[i]正好等于j，那么nums[0:i+1]中一定存在子数组和为j，因为新增的这个元素nums[i]就满足条件；

3.如果当前新增的元素nums[i]小于j，那么查看一下，nums[0:i]中是否存在子数组和为target-j，也就是查看一下dp[i-1][target-j]的值是否为True；

依据以上三个条件，可以方便地写出递推关系式。

最终返回矩阵最右下角的元素dp[len(nums-1)][target]即可。

class Solution():
    def canPartition(self, nums):
        if not nums:
            return False
        s = sum(nums)
        if s % 2 == 1:
            return False
        target = s // 2
        dp = [[False for _ in range(target+1)] for _ in range(len(nums))]
        if nums[0] <= target:
            dp[0][nums[0]] = True
        for i in range(1, len(nums)):
            for j in range(target+1):
                if dp[i-1][j] is True or nums[i] == j:
                    dp[i][j] = True
                elif nums[i] < j:
                    dp[i][j] = dp[i-1][j-nums[i]]

        return dp[len(nums)-1][target]

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析