class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
total=sum(nums)
if total&1!=0: return False
target=total>>1
dp=[False]*(target+1)
dp[0]=True
for num in nums:
#reverse the order to avoid use num multiple times
for i in reversed(xrange(num,target+1)):
dp[i]=(dp[i] or dp[i-num])
return dp[target]
网友评论