class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums) % 2 == 1:
return False
length = sum(nums) // 2 # 背包重量为 一半
dp = [0] * (length + 1)
for i in nums: # 先物品
for j in range(length, i-1, -1): # 再背包，01背包倒序避免重复放入
dp[j] = max(dp[j], dp[j-i]+i)
return dp[-1] == length # 如果恰好装满一半