题目
Given a non-empty array nums 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.
给一个堆正整数, 能不能把这组数分成2部分使得每部分的和一样. 比如给定[1, 5, 5, 11], 那么可以分成[1, 5, 5] 和 [11], 这样每组的和都是11, 就return true.
Bottom up dynamic programming 解法
暴力解法和combination一样, 就是找出这组数的所有子集, 也就是数学上说的幂集(power set). 也可以认为是武功秘籍的“秘籍”. 复杂度为O(2^n). 一般这种题最优解法肯定是我们的老朋友动态规划(dynamic programming), 可以通过避免重复计算把复杂度从指数降到多项式.
Python 2 代码
class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
isum = sum(nums)
if isum % 2 != 0:
return False
dp = [False] * (isum + 1)
dp[0] = True
for num in nums:
for part_sum in range(isum, -1, -1):
if dp[part_sum]:
dp[part_sum + num] = True
if dp[isum/2]:
return True
return False解释
用partial sum的可能值做dp不太容易想到, 这是背包问题的套路. 没见过想不出来应该是正常的, 不用觉得是自己菜. 毕竟第一个能想到解法的肯定都是高德纳教授(Donald Knuth)那样超级算法大神级别的. 遗憾的是我没找到这位大神是谁. 在coin change和coin change2里都是类似的套路.
空间复杂度: O(sum)
时间复杂度: O(sum * n)
原因: 两个for loop, 外面loop nums的数, 里面loop isum + 1个数, 总共2个乘起来
第一个loop从数组(比如 [1, 5, 5, 11])选一个出来, 也就是num, 然后检查在这个数以前被选中的数, 看他们的子集能加出的和, 也就是dp[part_sum], 加上这个数后dp[part_sum + num]肯定也是一个可能的和. 然后如果发现dp[sum/2]是可能的, 那么就说明这个数组可以被分成2部分使得每部分的和一样.
