题目
难度：★★★☆☆
类型：数组
方法：动态规划
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 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?我们有以下几个依据：
如果nums[0:i]中有子数组和为j（也就是dp[i-1][j]的值为True），则nums[0:i+1]中一定有子数组和为j，多了一个元素而已；
如果当前新增的元素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解决方案，请移步力扣中等题解析
