題目
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部分使得每部分的和一樣.
