描述
給一 只含有正整數(shù) 的 非空 數(shù)組, 找到這個數(shù)組是否可以劃分為 兩個 元素和相等的子集。
所有數(shù)組元素不超過100.
數(shù)組大小不超過200.
樣例
給一數(shù)組 [1, 5, 11, 5] , 返回 true ,
兩個子集:[1, 5, 5], [11]
給一數(shù)組 [1, 2, 3, 9] , 返回 false
代碼
class Solution:
"""
@param nums: a non-empty array only positive integers
@return: true if can partition or false
"""
def canPartition(self, nums):
# write your code here
sumNums = sum(nums)
n = len(nums)
if sumNums%2 != 0:
return False
m = sumNums//2
dp = [[False for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
dp[i][0] = True
for i in range(1, n+1):
for j in range(1, m+1):
if j<nums[i-1]:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]]
return dp[n][m]
思路
簡要而言怀愧，就是01背包問題的變種盈魁。首先腮考，數(shù)組總和是奇數(shù)，肯定是返回False的。然后掂林，數(shù)組是偶數(shù)和的情況下粘我，兩個子序列和相等鼓蜒，也就是說，需要我們找出其中一個子序列征字，它的和應(yīng)該為數(shù)組總和的一半都弹，如果這個子序列存在，那么數(shù)組中剩下的數(shù)就可以組成另一個子序列匙姜，其和必定也是數(shù)組總和的一半畅厢。所以問題就轉(zhuǎn)化了為01背包問題了，找到“體積”為數(shù)組中數(shù)字大小的石頭能剛好填滿“體積”為數(shù)組總和一半的背包氮昧，如果找到了框杜，就返回True，否則袖肥，F(xiàn)alse咪辱。
題目來源
https://www.lintcode.com/problem/partition-equal-subset-sum/description
