Partition Equal Subset Sum

主要还是要看出来这是个背包DP，其实就是问一个数能不能被数组里面的这些数组合起来，只是这个数是个特定的数而已

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        cumSum = sum(nums)
        if cumSum % 2:
            return False

        target = cumSum / 2
        n = len(nums)
        dp = [[False] * (target + 1) for _ in xrange(n)]

        for i in xrange(target + 1):
            dp[0][i] = 1 if i == nums[0] or not i else 0

        for i in xrange(1, n):
            for j in xrange(1, target + 1):
                dp[i][j] = dp[i - 1][j]
                if j >= nums[i]:
                    dp[i][j] |= dp[i - 1][j - nums[i]]

        return bool(dp[n - 1][target])