6-line Python DP Accepted - backpack


  • 1
    class Solution(object):
        def canPartition(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            total = sum(nums)
            dp = [True] + [False] * (total / 2)
            for i in xrange(1, len(nums) + 1):
                for j in reversed(xrange(1, total / 2 + 1)):
                    dp[j] = dp[j] or (j - nums[i - 1] >= 0 and dp[j - nums[i - 1]])
            return dp[-1] and not total % 2
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.