题解 | #分割等和子集#

dp,先判断整个数组的和 s 是否能被 2 整除,若不可以直接返回 False 若可以,则设置 dp 数组，确定状态转移方程, 该问题类似 0-1 背包 dp 的长度 为 s // 2, 状态转移时,当前状态只能从其大于nums[i] 的状态转移得到

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return bool布尔型
#
class Solution:
    def partition(self , nums: List[int]) -> bool:
        # write code here
        s = sum(nums)
        if s % 2: return False
        s = s // 2
        dp = [False for _ in range(s + 1)]
        dp[0] = True
        for i in range(len(nums)):
            for j in range(s, nums[i] - 1, -1):
                dp[j] = dp[j] or dp[j - nums[i]]
        return dp[-1]