题目描述：

LeetCode 416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Both the array size and each of the array element will not exceed 100.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

题目大意：

给定一个只包含正整数的非空数组，判断数组是否可以分成两个和相等的子数组。

注意：

数组长度与元素大小均不超过100

解题思路：

动态规划（Dynamic Programming）

利用数组dp[i]记录和为i的子数组是否存在，初始令dp[0] = 1

for num in nums:
    for i in range(sum(nums) - num + 1):
        if dp[i]: dp[i + num] = 1

Python代码：

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        sums = sum(nums)
        if sums & 1: return False
        nset = set([0])
        for n in nums:
            for m in nset.copy():
                nset.add(m + n)
        return sums / 2 in nset

 

本文链接：http://bookshadow.com/weblog/2016/10/09/leetcode-partition-equal-subset-sum/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码