Equal Sum Set

https://www.lintcode.com/problem/partition-equal-subset-sum/description?_from=ladder&&fromId=135

这题可以用backpack类似的模板只是，最大value的值被boolean value取代。

我们通过DP来判定是否最后背包的value能变成sum//2

另外i或j为0的edge case在最开始需要初始化值。

class Solution:
    """
    @param nums: a non-empty array only positive integers
    @return: true if can partition or false
    """
    def canPartition(self, nums):
        # write your code here
        s = sum(nums)
        if s % 2 != 0:
            return False 
            
        n = len(nums)
        s = s//2
        dp = [[False]*(s+1)  for _ in range(n)]
        for i in range(n):
            dp[i][0] = True 
        
        for j in range(1,s+1):
            dp[0][j] = nums[0] == j 
        
        
        for i in range(1,n):
            for j in range(1,s+1):
                if dp[i-1][j]:
                    dp[i][j] = dp[i-1][j]
                else:
                    if j >= nums[i]:
                        dp[i][j] = dp[i-1][j- nums[i]]
        
        return dp[n-1][s]