事实上，这是一个典型的“动态规划”问题，并且原型就是“0-1背包问题“，代码的执行过程就是在填表格的过程。但是做这题需要做一个等价转换，将问题看成：是否可以从数组中挑出一部分正整数使得这些数的和等于整个数组元素的和的一半，当然我们要先提前判断数组和是否能被2整除。本题和0-1背包问题有一个很大的不同，那就是0-1背包问题选取的物品的容积总量不能超过规定的总量，但本题所选取的数字之和责需要恰好等于规定的和的一半。这一点区别决定了在初始化的时候，所有的值应该初始化为 作为0-1背包问题，它的特点是：每个数只能用一次。思路是：物品一个一个选，容量也一点一点放大考虑。具体做法是：画一个len行，target+1列的表格。这里len是物品的个数，target是背包的容量。len行表示一个一个物品考虑，target+1多出来的那一列，表示背包容量从0开始
对这个动态规划问题的状态定义可以用dp[i][j]表示从数组的[0, i]这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于j。该问题的状态转移方程，很多时候，状态转移方程思考的角度是”分类讨论“，对于0-1背包问题而言就是当前考虑的数字选与不选。若不选择nums[i]，如果在[0, i-1]这个子区间内已经有一部分元素，使得它们的和为j，那么dp[i][j] = True，若选择nums[i]，如果在[0, i-1]这个子区间内就得找到一部分元素，使得它们的和为j - nums[i] 。状态转移方程可以写成dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]。写出状态转移方程后，需要考虑边界条件。首先j-nums[i]作为数组的下标，一定就得保证大于等于0，因此nums[i] <= j。其次，有一种特殊情况是j恰好等于nums[i]，即单独nums[j]这个数恰好等于此时背包的容积j，这也是符合题意的。因此，完整的状态转移方程是：
\[dp[i][j]= \begin{cases} dp[i-1][j], & 至少是这个答案，如果dp[i-1][j]为真没直接计算下一个状态 \\ true, & nums[i] = j \\ dp[i-1][j-nums[i]]. & nums[i] = j \end{cases} \tag{1}\]另外，在初始化时我们要将dp[0][0]设置成false，因为是正整数，当然凑不出和为0。输出为dp[len-1][target]，这里，len表示数组的长度，target是数组的元素之和（必须是偶数）的一半。这个算法的时间复杂度是O（NC），空间复杂度是O（NC），这里N是数组元素的个数，C是数组元素的和的一半。代码如1所示。
我们可以继续将代码进行一些简单的优化。我们注意到当容量为0的时候，即dp[i][0]按照本意来说，应该设置为false，但是注意到状态转移方程中有dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[j]]，当j-nums[i] == 0成立时，根据以上的分析，就说明单独的nums[i]这个数就恰好能分割为单独的一组，其余的数分割成另外一组，因此，我们把初始化的dp[i][0]设置成为true在代码运行层面是完全没问题的。观察状态转移方程的特点，or的结果只要为真，表格下面所有的值都为真（注意i和i-1），因此在填表的时候，只要表格的最后一列为true，代码就可以结束，直接返回true即可。因此我们可以将代码优化成如2所示。代码2的时间空间复杂度同上。
我们还能进一步做更大的优化，也是0-1背包问题的常规优化，即将状态数组从二维降到一维，减少空间复杂度。我们发现，在“填表格”的时候，当前行只参考了上一行的值，因此状态数组可以只设置2行，使用滚动数组的技巧填表格即可。实际上，连滚动数组都不必，在填表格的时候，当前行总是参考了它上面一行”头顶上“那个位置和“左上角”某个位置的值。因此我们可以只开一个一维数组并且从后向前依次填表即可。在从后往前的过程中，一旦nums[i] <= j不满足，可以马上退出当前循环，因为后面的j的值肯定越来越小，没有必要继续做判断，直接进入外层循环的下一层，也相当于一个剪枝，这一点是从前往后填表所不具备的。代码如3所示，该实现的时间复杂度为同上，但是空间复杂度变成了O（N）。
最后，关于为什么在状态压缩到一维之后要采用逆序，是因为在一维情况下是根据dp[j] or dp[j-nums[i]]来推dp[j]的值，如果不逆序就无法保证在外循环i值保持不变j值递增的情况下dp[j-nums[i]]的值不会被当前放入的nums[i]所修改，当值未达到临界条件时，会一直被nums[i]影响，也即是可能重复地放入了多次nums[i]，为了避免前面对后面产生影响，故用逆序。举个例子，数组为[2, 2, 3, 5]，要找和为6的组合，i=0时，dp[2]为真，当i自增到1，j = 4时，nums[i] = 2, dp[4] = dp[4] or dp[4 - 2]为true，当i不变，j = 6时, dp[6] = dp [6] or dp [6 - 2]，而dp[4]为true，所以dp[6] = true，显然是错误的。故必须得纠正在正序情况下，i值不变时多次放入nums[i]的情况。另外，值得补充的一点是，如果是正序的话，后面dp访问前面的dp时得到的是已经更新的内容，此时求的是完全背包问题。
21年1月再看这个题的时候，发现这题并不需要初始化，只要做一下如4的改变即可。:
class Solution:
def canPartition1(self, nums):
lennums = len(nums)
if lennums == 0:
return False
if sum(nums) % 2 == 1:
return False
target = sum(nums) // 2
res = [[False]*(target + 1) for i in range(lennums)]
if nums[0] <= target:
res[0][nums[0]] = True
for i in range(1, lennums):
for j in range(target+1):
res[i][j] = res[i-1][j]
if nums[i] == j:
res[i][j] = True
continue
if nums[i] < j:
res[i][j] = res[i-1][j-nums[i]] or res[i-1][j]
return res[-1][-1]
def canPartition2(self, nums):
lennums = len(nums)
sumnums = sum(nums)
if lennums == 0:
return False
if sumnums % 2 == 1:
return False
target = sumnums // 2
dp = [[False]*(target+1) for i in range(lennums)]
dp[0][0] = True
if nums[0] <= target:
dp[0][nums[0]] = True
for i in range(1, lennums):
for j in range(target+1):
dp[i][j] = dp[i-1][j]
if nums[i] <= j:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
if dp[i][-1]:
return True
return dp[-1][-1]
def canPartition3(self, nums):
lennums = len(nums)
sumnums = sum(nums)
if lennums == 0:
return False
if sumnums % 2 == 1:
return False
target = sumnums // 2
res = [False]*(target+1)
res[0] = True
if nums[0] <= target:
res[nums[0]] = True
for i in range(1, lennums):
for j in range(target, nums[i]-1, -1):
if res[target]:
return True
res[j] = res[j-nums[i]] or res[j]
return res[-1]
def canPartition4(self, nums: List[int]) -> bool:
size = len(nums)
if size == 0:
return False
s = sum(nums)
if s % 2 == 1:
return False
target = s // 2
dp = [False]*(target+1)
for i in range(size):
for j in range(target, nums[i]-1, -1):
dp[j] = dp[j] or dp[j-nums[i]]
if dp[-1]:
return True
if nums[i] <= target:
dp[nums[i]] = True
return dp[-1]