416. 分割等和子集

Difficulty
Medium
Tags
动态规划
URL
https://leetcode-cn.com/problems/partition-equal-subset-sum/
Star
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
提示：
  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

法1 动态规划 二维DP

思路
经典的背包问题，考虑每个物品拿或者不拿，最后能不能装成sun(nums)//2的背包
状态定义及转移：
dp[i][j] 表示前i个物品 nums[0:i]能否装成 重量为j的。
转移： dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
初始化：
dp[i][0] 表示装成重量为0 的。显然，只要不拿就满足了，所以dp[i][0] = True
题解
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_ = sum(nums)
        if sum_ % 2 == 1:
            return False

        target = sum_ // 2

        dp = [[False] * (target+1) for _ in range(len(nums)+1)]
        
        # 初始化， 目标和为0 ，不放所有物品即可
        for i in range(0, len(dp)):
            dp[i][0] = True

        for i in range(1, len(nums)+1):
            for j in range(1, target+1):
                # 考虑第 i 个物品
                if j - nums[i-1] >= 0:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
                # 不考虑 第 i 个物品，那么和前i-1个物品的状态相同
                else:
                    dp[i][j] = dp[i-1][j]

        return dp[-1][-1]
优化：上述 dp[i] 之和前一个 dp[i-1] 有关，所以 考虑只创建一维dp数组：
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_ = sum(nums)
        if sum_ % 2 == 1:
            return False
        target = sum_ // 2

        dp = [False] * (target+1)
        dp[0] = True  # 啥也不装就能满足

        # 遍历状态
        for i in range(1, len(nums)+1):
            temp = [False] * (target+1)
            for j in range(1, target+1):
                # 做决策
                # 默认 不考虑当前物品
                temp[j] = dp[j]
                # 能考虑的话，再考虑当前物品
                if j - nums[i-1] >= 0:
                    temp[j] = temp[j] or dp[j-nums[i-1]]
            
            dp = temp
        
        return dp[target]

法2 动态规划 一维DP

思路
创建最大容量为 sum(nums) // 2 的dp数据
dp[i] : 容量为 i 的背包最大可装 的数值和为 dp[i]， 那么最后如果dp[target] == target ，则说明可以等分。
notion imagenotion image
notion imagenotion image
题解：
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_ = sum(nums)
        if sum_ % 2 == 1:
            return False

        target = sum_ // 2
        dp = [0] * (target+1) # dp[i] 容量为 i的背包最大可装 数值和为 dp[i]
        for num in nums:
            for j in range(target, num-1, -1):
                dp[j] = max(dp[j], dp[j-num]+num)
        
        return dp[-1] == target