LeetCode 第 416 题：“分割等和子集”题解
题解地址：0-1 背包问题 + 针对本题的优化（Python 代码、Java 代码）。
说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。
传送门：416. 分割等和子集。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
0-1 背包问题 + 针对本题的优化（Python 代码、Java 代码）
看到题目，首先想一想题目为什么要告诉你是正整数，有 0 的话行不行，是实数行不行，是负数行不行。
回答：实际上做以上限制了是降低了难度的。
- 有 0 当然可以啦，不过 0 的存在意义不大，放在哪个子集都是可以的；
- 再说实数，实数有可能是无理数，也可能是无限不循环小数，因为我们要计算整个数组元素的和的一半，在做除法，然后在比较两个子集元素的和是否相等的时候，就会遇到精度的问题；
- 再说负数，负数其实也是可以存在的，但是你可能要用搜索（回溯）的办法去完成这道题了。
再看看题目给出的“注意”：
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
简单计算一下：数组元素的和最大是 ，不是很大，现代计算机可以轻松完成这个级别的运算。我想分析到这里，不难看出，题目给的这些条件和“注意”就是在暗示你使用“动态规划”了。
方法一：动态规划
这是一道以 0-1 背包问题为背景的算法练习题，我们把这个题目翻译一下：
给定一个只包含正整数的非空数组。是否可以从这个数组中挑选出一些正整数，每个数只能用一次，使得这些数的和等于整个数组元素的和的一半。
0-1 背包问题也是最基础的背包问题，它的特点是：待挑选的物品有且仅有一个，可以选择也可以不选择。下面我们定义状态，不妨就用问题的问法定义状态试试看。
dp[i][j] ：表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和等于 j。
根据我们学习的 0-1 背包问题的状态转移推导过程，新来一个数，例如是 nums[i]，根据这个数可能选择也可能不被选择：
- 如果不选择
nums[i]，在[0, i - 1]这个子区间内已经有一部分元素，使得它们的和为j，那么dp[i][j] = true； - 如果选择
nums[i]，在[0, i - 1]这个子区间内就得找到一部分元素，使得它们的和为j - nums[i]，我既然这样写出来了，你就应该知道，这里讨论的前提条件是nums[i] <= j。
以上二者成立一条都行。于是得到状态转移方程是：
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]], (nums[i] <= j)
于是按照 0-1 背包问题的模板，我们不难写出以下代码。
参考代码 1：
Python 代码：
from typing import List
class Solution:
def canPartition(self, nums: List[int]) -> bool:
size = len(nums)
# 特判
if size == 0:
return False
# 特判，如果整个数组的和都不是偶数，就无法平分
s = sum(nums)
if s & 1 == 1:
return False
# 二维 dp 问题：背包的容量
target = s // 2
dp = [[False for _ in range(target + 1)] for _ in range(size)]
# 先写第 1 行：看看第 1 个数是不是能够刚好填满容量为 target
for i in range(target + 1):
dp[0][i] = False if nums[0] != i else True
# i 表示物品索引
for i in range(1, size):
# j 表示容量
for j in range(target + 1):
if j >= nums[i]:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
else:
dp[i][j] = dp[i - 1][j]
return dp[-1][-1]
Java 代码：
public class Solution {
/**
* 常规 0-1 背包问题的写法
*
* @param nums
* @return
*/
public boolean canPartition(int[] nums) {
int size = nums.length;
if (size == 0) {
return false;
}
int s = 0;
for (int num : nums) {
s += num;
}
// 特判 2：如果是奇数，就不符合要求
if ((s & 1) == 1) {
return false;
}
int target = s / 2;
// 创建二维状态数组，行：物品索引，列：容量
boolean[][] dp = new boolean[size][target + 1];
// 先写第 1 行
for (int i = 1; i < target + 1; i++) {
if (nums[0] == i) {
dp[0][i] = true;
}
}
for (int i = 1; i < size; i++) {
for (int j = 0; j < target + 1; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= nums[i]) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
}
}
}
return dp[size - 1][target];
}
}
复杂度分析：
- 时间复杂度：：这里 是数组元素的个数， 是数组元素的和的一半。
- 空间复杂度：。
我们学习过的 0-1 背包问题，是可以状态数组从二维降到一维，从而减少空间复杂度。
优化一：从二维降到一维，减少空间复杂度
在编写的过程中，我们还发现：
1、填写第 1 个物品是否满足状态的时候，因为 nums[0] 是不变的，而 j 在不断增加，只要满足 nums[0] == j 成立，后面的 j 就不必做判断了，因为一定有 nums[0] < j 成立；
2、从后向前写的过程中，一旦 j >= nums[i] 不满足，可以马上退出当前循环，因为后面 j 肯定越来越小，没有必要继续做判断，直接进入外层循环的下一层。
以下代码根据上面的“参考代码 1”修改，修改和需要注意的地方，我都加了注释。
参考代码 2：
Python 代码：
from typing import List
class Solution:
def canPartition(self, nums: List[int]) -> bool:
size = len(nums)
if size == 0:
return False
s = sum(nums)
if s & 1 == 1:
return False
# 从第 2 行以后，当前行的结果参考了上一行的结果，因此使用一维数组定义状态就可以了
target = s // 2
dp = [False for _ in range(target + 1)]
# 看看第 1 个数是不是能够刚好填满容量为 target
for j in range(target + 1):
if nums[0] == j:
dp[j] = True
# 如果等于，后面就不用做判断了，因为 j 会越来越大，肯定不等于 nums[0]
break
# 注意：因为后面的参考了前面的，我们从后向前计算
for i in range(1, size):
for j in range(target, -1, -1):
if j >= nums[i]:
dp[j] = dp[j] or dp[j - nums[i]]
else:
# 后面的容量越来越小，因此没有必要再判断了，退出当前循环
break
return dp[-1]
Java 代码：
public class Solution2 {
public boolean canPartition(int[] nums) {
int size = nums.length;
if (size == 0) {
return false;
}
int s = 0;
for (int num : nums) {
s += num;
}
if ((s & 1) == 1) {
return false;
}
int target = s / 2;
// 从第 2 行以后，当前行的结果参考了上一行的结果，因此使用一维数组定义状态就可以了
boolean[] dp = new boolean[target + 1];
// 先写第 1 行，看看第 1 个数是不是能够刚好填满容量为 target
for (int j = 1; j < target + 1; j++) {
if (nums[0] == j) {
dp[j] = true;
// 如果等于，后面就不用做判断了，因为 j 会越来越大，肯定不等于 nums[0]
break;
}
}
// 注意：因为后面的参考了前面的，我们从后向前填写
for (int i = 1; i < size; i++) {
// 后面的容量越来越小，因此没有必要再判断了，退出当前循环
for (int j = target; j >= 0 && j >= nums[i]; j--) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[target];
}
}
复杂度分析：
- 时间复杂度：：这里 是数组元素的个数， 是数组元素的和的一半。
- 空间复杂度：：减少了物品那个维度，无论来多少个数，用一行表示状态就够了。
优化二：注意到本题的特殊性，提前结束循环
1、如果你跟我一样写题解的话，你可能会在纸上画一个表格：
你可以在“参考代码 1”那里把状态数组打印出来，如下：
[False, True, False, False, False, False, False, False, False, False, False, False]
[False, True, False, False, False, False, True, False, False, False, False, False]
[False, True, False, False, False, False, True, False, False, False, False, False]
[False, True, False, False, False, False, True, False, False, False, False, True]
我发现是初始值设置有问题，dp[0][0] 应该设置成 True，还记得我们最开始的时候，注意到数组给出的是“正整数”这个条件吗？再看看状态转移方程：
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]], (nums[i] <= j)
当 nums[i] 刚刚好等于容量 j 的时候，就会去看 dp[i][0] ，显然，从语义上说，nums[i] 可以成为一个子集，而剩下的数成为另一个子集，因此 dp[i][0] 应该设置成为 True。
2、我还发现，从第 2 行开始，当前行先把前一行抄下来，然后再根据状态转移方程：
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]], (nums[i] <= j)
去修改当前行的值，很神奇的一点是，这个状态转移方程中间的逻辑运算符是 or，or 的特点是：只要其中之一为 True，那么整个表达式就为 True，那就更简单啦，我只要在填写每一行的最后一个数的时候，我发现最后一个数的值是 True，我就可以直接结束整个代码，返回 True，因为我们填表是从后向前填的，因此我们把这个判断放在一行的开头。
于是我又修改了代码。以下代码根据上面的“参考代码 2”修改，修改和需要注意的地方，我都加了注释。
参考代码 3：
Python 代码：
from typing import List
class Solution:
def canPartition(self, nums: List[int]) -> bool:
size = len(nums)
if size == 0:
return False
s = sum(nums)
if s & 1 == 1:
return False
target = s // 2
dp = [False for _ in range(target + 1)]
# 状态转移方程：dp[i - 1][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
# 单独 1 个数可以构成子集，根据状态转移方程，当 j == nums[i] 成立的时候，会来看 dp[i - 1][0] 的值
# 因此根据语义，dp[0] 应该设置为 True
dp[0] = True
for j in range(target + 1):
if nums[0] == j:
dp[j] = True
break
for i in range(1, size):
# 先看最后一个数是不是返回 True，如果是后面就没有必要计算了，方法可以直接返回 True
dp[-1] = dp[-1] or dp[target - nums[i]]
if dp[-1]:
return True
# 然后再写倒数第 2 个数，倒数第 3 个数
for j in range(target - 1, -1, -1):
if j >= nums[i]:
dp[j] = dp[j] or dp[j - nums[i]]
else:
break
return dp[-1]
Java 代码：
public class Solution {
public boolean canPartition(int[] nums) {
int size = nums.length;
if (size == 0) {
return false;
}
int s = 0;
for (int num : nums) {
s += num;
}
if ((s & 1) == 1) {
return false;
}
int target = s / 2;
boolean[] dp = new boolean[target + 1];
// 状态转移方程：dp[i - 1][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
// 单独 1 个数可以构成子集，根据状态转移方程，当 j == nums[i] 成立的时候，会来看 dp[i - 1][0] 的值
// 因此根据语义，dp[0] 应该设置为 True
dp[0] = true;
for (int j = 1; j < target + 1; j++) {
if (nums[0] == j) {
dp[j] = true;
break;
}
}
for (int i = 1; i < size; i++) {
// 先看最后一个数是不是返回 True，如果是，后面就没有必要计算了，方法可以直接返回 True
if(target >= nums[i]){
dp[target] = dp[target] || dp[target - nums[i]];
}
if (dp[target]) {
return true;
}
// 然后再写倒数第 2 个数，倒数第 3 个数
for (int j = target - 1; j >= 0 && j >= nums[i]; j--) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[target];
}
}
代码写到这里，能拿到一个还不错的排名。
复杂度分析：
- 时间复杂度：：这里 是数组元素的个数， 是数组元素的和的一半。
- 空间复杂度：。