首页 > 代码库 > 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