LeetCode 416. 分割等和子集

题目

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

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

方法：动态规划

想要求得进行数组一分为二后是否存在两个子集使得他们他们的元素和相等，那么每个子集的元素和应为原数组元素和的一半

• target 表示数组元素和，起始值为原数组的元素和
• 判断该元素和 target 是否为单数，因为原数组的元素均为正整数，若为单数，那么无论怎样分割都无法得到两个元素和相等的子集，返回 False
• target 更新为若可以分割成两个元素和相等的子集的元素和，即原数组元素和的一半
• dp[j] 表示背包容量为 j，最大可以凑成 j 的子集元素和为 dp[j]。因为为正整数数组，所以初始化为 0，并且 dp 的长度为 target + 1
• 外循环表示对数组的遍历，遍历顺序为正序；内循环表示对背包容量的遍历，遍历顺序为倒序
  ※倒序循环的原因： 保证物品 i 只被放入背包一次，若正序遍历则会导致同意物品重复放入背包
  例：
  nums = [1,5,11,5]
  dp[0] = 0
  dp[1] = dp[1-nums[0]] + nums[0] = 5
  dp[2] = dp[2-nums[0]] + nums[0] = 5
  dp[3] = dp[3-nums[0]] + nums[0] = 5
  dp[4] = dp[4-nums[0]] + nums[0] = 5
  dp[5] = dp[5-nums[0]] + nums[0] = 5
  dp[6] = dp[6-nums[0]] + nums[0] = 10
  我们可以发现 nums[0] 被放入了两次
• 递推公式：dp[j-nums[i]] 表示容量为 j-nums[i] 的背包最大可以凑成 j-nums[i] 的子集元素和，dp[j-nums[i]] + nums[i] 则表示容量为 j 的背包在放入了 i 后的子集元素和。那么此时的 dp[j] 则有两个选择：不放 i，即原 dp[j]；放 i，即 dp[j-nums[i]] + nums[i]，选择最大的那个
• 若子集的元素和 target 等于实际的最大可以凑成 target 的子集元素和 dp[target]，那么返回 True；否则，即 target 小于 dp[target]，返回 False

class Solution(object):
    def canPartition(self, nums):
        target = sum(nums)
        if target % 2 == 1:
            return False
        target //= 2
        dp = [0] * (target + 1)
        for i in range(len(nums)):
            for j in range(target, nums[i] - 1, -1):
                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
        return target == dp[target]

相关知识

• 除法：
  /： 常规数学计算
  //： 若除数和被除数均为正数或负数，则取商；若除数和被除数一个为正数一个为负数，则向下取余
  

参考

代码相关：https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html#_416-%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86
除法：https://m.php.cn/article/475783.html