225 - 416 分割等和子集

题目

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

注意:

每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

解答

参考01背包问题和李威威大佬的解答

https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/0-1-bei-bao-wen-ti-xiang-jie-zhen-dui-ben-ti-de-yo/

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        target = sum(nums)
        if target % 2 != 0:
            return False
        target //= 2
        dp = [[False]*(target+1) for _ in range(n)]
        dp[0][0] = True
        for i in range(1, target+1):
            if nums[0] == i:
                dp[0][i] = True
                break
        for i in range(1, n):
            for j in range(target+1):
                if j >= nums[i]:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[-1][-1]

Runtime: 1676 ms, faster than 25.09% of Python3 online submissions for Partition Equal Subset Sum.

Memory Usage: 16.3 MB, less than 9.09% of Python3 online submissions for Partition Equal Subset Sum.

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        target = sum(nums)
        if target % 2 != 0:
            return False
        target //= 2
        dp = [False]*(target+1)
        dp[0] = True
        for i in range(1, n):
            for j in range(target, nums[i]-1, -1):
                dp[j] = dp[j] or dp[j-nums[i]]
        return dp[-1]

Runtime: 780 ms, faster than 48.92% of Python3 online submissions for Partition Equal Subset Sum.

Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Partition Equal Subset Sum.