416. 分割等和子集 -- 01背包问题

416. 分割等和子集

这道题其实就是一个01背包问题，关于背包问题的相关实现见：

1. 01背包问题 – 动态规划
2. 完全背包问题

class CanPartition:
    """
    416. 分割等和子集
    https://leetcode.cn/problems/partition-equal-subset-sum/
    """
    def solution(self, nums: List[int]) -> bool:
        """
        其实这道题就是一个 01背包问题，数组求和为sum
        相当于给定背包的容量为sum/2，物品为nums，问能否有一种装法，把背包恰好装满？
        :param nums:
        :return:
        """
        nums_sum = sum(nums)
        if nums_sum % 2 != 0:
            return False
        pack = int(nums_sum/2)
        n = len(nums)
        # dp[i][j] 表示：对于前i个物品（i从1开始计数），背包容量为 j 时，是否恰好能把背包填满。
        dp = [[False for _ in range(pack+1)] for _ in range(n+1)]

        # base case
        for i in range(n+1):
            dp[i][0] = True

        # 自底向上
        for i in range(1, n+1):
            for j in range(1, pack+1):
                if j - nums[i-1] < 0:
                    # 背包容量不足，不能装入第 i 个物品
                    dp[i][j] = dp[i-1][j]
                else:
                    # 装入或不装入
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]

        return dp[len(nums)][pack]

    def solution2(self, nums: List[int]) -> bool:
        """
        注意到dp[i][j] 都是从 dp[i-1][..] 转移过来的，之前的数据不会再用了，因此，
        可以将二维数组压缩为一维
        :param nums:
        :return:
        """
        nums_sum = sum(nums)
        if nums_sum % 2 != 0:
            return False
        pack = int(nums_sum / 2)
        n = len(nums)
        # dp[j] 表示：背包容量为 j 时，是否恰好能把背包填满。
        dp = [False for _ in range(pack + 1)]

        # base case
        dp[0] = True

        for i in range(n):
            # 注意，这里 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能⽤⼀次，以免之前的结果影响其他的结果。
            for j in range(pack, -1, -1):
                if j - nums[i] >= 0:
                    #  装入或不装入
                    dp[j] = dp[j] or dp[j - nums[i]]

        return dp[pack]