无标题文章

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]