canPartition

Leetcode

---

题目分析：变式的0-1背包问题，背包空间是数组值和的一半，物件是数值，每一步选择或不选择当前数
最后的结果使得在该背包空间下，有无子数组、即选取后能刚好等于空间值。
初始化数组皆为False。对数组求和，若和是奇数，则必然无法平分。
那么，若能平分，即存在两个子数组的和相同，换言之，便是数组中的数必然是要分到其中之一。
解题时，以第一个数所在子数组为我所求的子数组。那么必然在遍历背包空间时，存在可以刚好存放的空间数。
令该空间为$True$。然后再从第二行开始往后遍历，当空间数大于等于该数值时，根据上一状态的结果(不包含当前值)或者是
添加当前值的结果进行判断。状态转移方程为：

$$Bag[i][j]=Bag[i-1][j]\ or\ Bag[i-1][j-num[i]]$$ 整体状态转移方程为：

$$\begin{equation} Bag[i][j]= \begin{cases} Bag[i-1][j]& \text {j<num[i]}\\[2ex] Bag[i-1][j]\ or\ Bag[i-1][j-num[i]]& \text {j>=num[i]}\\ \end{cases} \end{equation}$$

'''
# File: canPartition.py
# Author: 0HP
# Date: 20200204
# Purpose: solve the problem in website: https://leetcode.com/problems/partition-equal-subset-sum/
'''
class Solution:
    def canPartition(self, nums: []) -> bool:
        numcounts=len(nums)
        numsum=sum(nums)
        #if the sum of the list is odd, it must can not be part
        if numsum&1 or numcounts<2:
            return False
        weight=numsum//2
        Bag=[[False for i in range(weight+1)]for i in range(numcounts+1)]
        for i in range(weight+1):
            if nums[0]==i:
                Bag[1][i]=True
        for i in range(2,numcounts+1):
            for j in range(weight+1):
                if not j<nums[i-1]:
                    Bag[i][j]=Bag[i-1][j] or Bag[i-1][j-nums[i-1]]
                else:
                    Bag[i][j]=Bag[i-1][j]
        return Bag[-1][-1]
t=Solution()
l=[1,5,11,5]
print(t.canPartition(l))