代码随想录算法训练营第四十二天| LeetCode416. 分割等和子集

一、LeetCode416. 分割等和子集

        1：题目描述（416. 分割等和子集）

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

        2：解题思路

        本题需要使用01背包的解题思路

        什么事01背包呢，参考下面的链接

        0-1背包基础理论一：

        文章详解：代码随想录

        视频讲解：

带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法_哔哩哔哩_bilibili

        0-1背包理论基础二：

        文章详解：代码随想录

        视频讲解：带你学透01背包问题（滚动数组篇） | 从此对背包问题不再迷茫！_哔哩哔哩_bilibili

        代码展示：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 使用01背包思路，可以把nums数组中的元素看成物品，物品的重量和价值都是元素的值
        # 使用一维数组，dp[j]，表示容量为j的背包最大价值是dp[j]
        # 根据01背包，一维数组的推导公式dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
        # weight[i],value[i]分别表示物品的重量和价值
        # 可以得出本题的推导公式，dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
        # 
        # 要想分割成两个子集，并且元素相等，则nums得为偶数
        # 每个子集的和为nums元素和的一半
        target = sum(nums)    # 求nums的和
        if target % 2 != 0:
            return False    # 若nums的和不是偶数，则无法分割成两个子集的元素和相等
        target = int(target/2)
        print(target)
        # 初始化
        dp = [0] * (target+1)
        # 遍历顺序
        for i in range(len(nums)):
            for j in range(target, 0, -1):
                if j < nums[i]: 
                    # 当背包容量小于物品i的重量时，无法放入物品i
                    dp[j] = dp[j]
                else:
                    # 当背包容量大于等于物品i的重量时，可以放入物品i
                    dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
        print(dp)
        if dp[target] == target:
            # 当最后的背包容量所装的最大价值，等于目标价值
            # 即当子集的元素和，等于目标和，就找到了符合要求的两个子集，返回True
            return True
        else:
            # 不等，说明找不到两个子集的和相等
            return False