LeetCode(力扣)416. 分割等和子集Python

题目链接

https://leetcode.cn/problems/partition-equal-subset-sum/

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum = 0
        dp = [0]*10001
        for num in nums:
            sum += num
        if sum % 2 == 1:
            return False
        target = sum //2
        for num in nums:
            for i in range(target, num - 1, -1):
                dp[i] = max(dp[i], dp[i - num] + num)
        
        if dp[target] == target:
            return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16