【LeetCode 】416. 分割等和子集（0-1背包）逐行注释详解
1. 题目说明
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
2. 解题思路
本题的重难点，是将其转化为 0-1 背包问题。
对于给定的数组中每一个元素，选择或者不选，使其能够恰好装满容量为 target // 2的背包
dp[ i ][ j ]表示 在区间 [ 0, i ] 中任取几个数(每个数都可以取或者不取)，恰好能装满 容量 j 的包
- 特判，若 target 为奇数，直接返回 False
- 令 target = target // 2
- 初始化 dp = [[False,⋯,False],⋯,[False,⋯,False]]，维度为n*(target+1)
- 初始化第 0 行，令 dp[ 0 ][ 0 ] = True （可以理解为背包容量为 0 时，可以 “不选择” 第 0 个物品，那就“恰好可以装满”）
- 遍历第 0 行，将第 0 个物品恰好可以装满的容器置为 True
- 循环遍历整个表
3. 代码详解
3.1 二维 dp
Python
class Solution:
def canPartition(self, nums: List[int]) -> bool:
""" 0-1背包 二维 dp "恰好装满背包的问题"，初始化的时候只能让dp[0][0]为True (合法)， 其他为False (不合法)，在经典背包问题中，恰好装满的话，是dp[0][0]=0, dp[0][0,...V]=-inf 参考 https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/dong-tai-gui-hua-kong-jian-you-hua-zhu-xing-jie--2/ dp[i][j] 背包剩余容量为j的时候，恰好装前i件物品, 或者描述为"表示在前i个物品（元素）选或者不选可以装满容量j的背包。" dp[0][0] = True 可以理解为，当"不选"第一个(index = 0)物品的时候，恰好可以装满容量为 0 的背包 """
n = len(nums)
target = sum(nums)
if (target % 2 != 0): # 奇数，无法均分两份
return False
target = target // 2 # 走到这一步就是偶数，除半
# 二维数组，行数n是物品索引（不包含 no item），列数target+1 （包含0）
dp = [[False]*(target+1) for _ in range(n)]
dp[0][0] = True
# 第0行，第一个数恰好只能让容积为它的背包恰好装满
# 所以最终dp数组的第0行只有dp[0][0]和dp[0][nums[0]]是true，其他都是默认的初始值false
if nums[0] <= target: # 单个数不能超过 target
dp[0][nums[0]] = True
for i in range(1, n): # [1,..., n-1]
for j in range(0, target+1): # [0, target]
if (j < nums[i]): # 容量太小
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]]
#print(dp)
return dp[-1][-1]
3.2 一维 dp （空间优化）
二维dp的题目，一般可以通过压缩空间的方式进行优化。
注意：
在转成一维 dp 时，j 的遍历顺序是 逆序的，逆序可以解决正序遍历值覆盖的问题。具体描述在另一篇博客 中有详细说明：
Python
# 一维 dp 有三种方法，一步步推进
class Solution:
def canPartition(self, nums: List[int]) -> bool:
""" 0-1背包 一维 dp """
n = len(nums)
target = sum(nums)
if (target % 2 != 0): # 奇数，无法均分两份
return False
target = target // 2 # 走到这一步就是偶数，除半
# 二维数组，行数n是物品索引（不包含 no item），列数target+1 （包含0）
dp = [False]*(target+1)
dp[0] = True
if nums[0] <= target: # 单个数不能超过 target
dp[nums[0]] = True
for i in range(1, n): # [1,..., n-1]
########################### 法【1】############################
# for j in range(target, -1, -1): # [target, 0]
# if (j < nums[i]): # 容量太小
# dp[j] = dp[j] # 由于每次操作对dp[j]值并没改变，所以可以直接去掉。如果是 dp[j]=dp[j]+1这种，那就不能直接去掉这句话了
# else:
# dp[j] = dp[j] or dp[j-nums[i]]
############################ 法【2】###########################
# for j in range(target, -1,-1): # [target, 0]
# if j >= nums[i]:
# dp[j] = dp[j] or dp[j-nums[i]]
########################### 法【3】############################
for j in range(target, nums[i]-1, -1): # [target,...,nums[i]] 逆序
dp[j] = dp[j] or dp[j-nums[i]]
#######################################################
return dp[-1]
输出结果
本题更准确的理解是：
dp[i][j]表示 在区间[0, i]中任取几个数(每个数都可以取或者不取)，恰好能装满 容量 j
========================================================================================================
[index(i)]
[capacity(j)] 0 1 2 3 4 5 6 7 8 9 10 11
1 0 T T
5 1 T T T T
11 2 T T T T T
5 3 T T T T T T
========================================================================================================
说明：上表中“T”表示 True，未填的 均为 “False”
