LintCode-划分和相等的子集-动态规划

描述

给一 只含有正整数 的 非空 数组, 找到这个数组是否可以划分为 两个 元素和相等的子集。

所有数组元素不超过100.
数组大小不超过200.

样例

给一数组 [1, 5, 11, 5] , 返回 true ,
两个子集:[1, 5, 5], [11]
给一数组 [1, 2, 3, 9] , 返回 false

代码

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
        sumNums = sum(nums)
        n = len(nums)
        if sumNums%2 != 0:
            return False
        m = sumNums//2
        dp = [[False for j in range(m+1)] for i in range(n+1)]
        for i in range(n+1):
            dp[i][0] = True
        for i in range(1, n+1):
            for j in range(1, m+1):
                if j<nums[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]]
        return dp[n][m]

思路

简要而言，就是01背包问题的变种。首先，数组总和是奇数，肯定是返回False的。然后，数组是偶数和的情况下，两个子序列和相等，也就是说，需要我们找出其中一个子序列，它的和应该为数组总和的一半，如果这个子序列存在，那么数组中剩下的数就可以组成另一个子序列，其和必定也是数组总和的一半。所以问题就转化了为01背包问题了，找到“体积”为数组中数字大小的石头能刚好填满“体积”为数组总和一半的背包，如果找到了，就返回True，否则，False。

题目来源

https://www.lintcode.com/problem/partition-equal-subset-sum/description