首页 > 代码库 > 416. Partition Equal Subset Sum

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: trueExplanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]Output: falseExplanation: The array cannot be partitioned into equal sum subsets.

代码:

今天赶上周末,LeetCode又提示contest开始了,一直没有勇气去做,今天看了下,第一题,好简单,两个字符串转换成数字相加。

瞬间有了信心,于是开始研究这个题目,判断两个数组是否可以分成和相同的两部分,看起来貌似不难哦。

首先当然是所有元素相加除2了,为偶数才有可能嘛,当然,必须有足够的元素和为这个值。

想想,穷举一下,遍历所有情况不就可以了吗?

可是写啊写啊,循环、递归,逻辑总是想不清楚,折腾到contest结束。

无奈百度了一下,大神早已完成博客,python下竟然只用了6、7行代码!!!

参考:http://bookshadow.com/weblog/2016/10/09/leetcode-partition-equal-subset-sum/

贴过来供大家一起学习:动态规划的思想

        sums = sum(nums)
        if sums & 1: return False
        nset = set([0])
        for n in nums:
            for m in nset.copy():
                print ‘n:‘+str(n)+‘ ‘+‘m:‘+str(m)
                nset.add(m + n)
                print nset
        return sums / 2 in nset

大神果然是大神!还有很长路要走喽!

416. Partition Equal Subset Sum