42天【代码随想录算法训练营34期】第九章 动态规划part04(● 01背包问题，你该了解这些！ ● 01背包问题，你该了解这些！ 滚动数组 ● 416. 分割等和子集 )

**416. 分割等和子集 **

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
        #target = 11

        for num in nums:
            #1, 5, 11, 5
            for j in range(target, num-1, -1):
                dp[j] = max(dp[j], dp[j-num] + num)
                # 11， 0， -1 【1,1,1,1,1,..., 1,1】
                # 11, 4, -1 [1, 1, 1, 1, 1, 5, 6, ...., 6]
                # 11, 10, -1
                # 11, 4, -1 [...11]
                # 每个背包最多能承多少                
        
        if dp[target] == target:
            return True
        return False