「力扣」第 416 题：“分割等和子集”_力扣416c语言

大家好，这里是“力扣”视频题解第 416 题：“分割等和子集”。

这道题给了我们一个只包含正整数的非空数组。问我们是否可以将这个数组分割成两个子集，使得这两个子集的元素的和相等。

我们看示例 1：给出的数组是 [1, 5, 11, 5]，这个数组中所有元素之和是 22，示例中给出的分割是 [1, 5, 5] 和 [11]。

从这个示例中我们知道：

1、分割的两个部分是子集，并不要求是数组中连续的一部分；
2、分割的两个子集的拼接起来是整个数组，并且每个元素只能使用一次；
3、单独的一个元素也可以称为一个子集，但是空元素和全部元素就不能称为一个子集，这一点应该不难想明白。

解决这个问题我们需要一些“动态规划”问题的基本知识，事实上这个问题我们只要稍加分析，就不难看出，它是动态规划的典型问题：“0-1 背包问题”的变形问题。

从题意和给出的示例中不难看出，题目就是要我们从给出的数组中找出一个非空的子集作为一个分割，这个子集的和为全部元素的和的一半，剩下的没有被选出的元素就作为另一半分割，这两个分割的和显然是相等的。

在若干个物品中选出一定的物品，每个物品只能使用一次，这些物品恰好能够填满容量为 sum / 2 的背包。

而“0-1 背包问题”是这样描述的：

在 M 件物品取出若干件放在体积为 W 的背包里，每件物品只有一件，它们有各自的体积和价值，问如何选择使得背包能够装下的物品的价值最多。

这里要向大家说明的是：

1、len 是数组的长度，可以认为是背包里物品的个数；
2、sum 是数组里所有元素的和，我们要选出的若干个元素之和为 sum / 2，那么没有被选出的元素之和也为 sum / 2，我们注意到题目中给出的数组只包含正整数，因此 sum 如果是奇数，那么 sum / 2 是一个带 0.5 的小数，一定不会存在一个全是整数的子集，它的和是一个小数，这一点是一个特殊判断；

3、根据“0-1 背包问题”的经验，我们的思路是：一个一个物品去尝试，一点一点扩大考虑能够容纳的容积的大小（这一点很重要），整个过程就像是在填写一张二维表格。

因此，我们从思路上就应该转变过来，我们需要考虑的就是从一个长度有限的数组 nums 中，拿出一部分元素，求出这些元素的和是否恰好等于某一个定值 target = sum / 2。

4、根据求解动态规划问题的一般步骤。

（1）首先设置状态。

状态定义：dp[i][j] 考虑下标 [0, i] 这个区间里的所有整数，在它们当中是否能够选出一些数，使得这些数之和恰好为整数 j。

注意：这个 i 是具有前缀性质的，我们虽然只写一个数字，但是它表示的含义是我们考虑的是子区间 [0, i] 里的所有元素，下标 i 以及 i 以前的元素在我们的考虑范围之内，下标 i 之后的元素一定不在我们的考虑范围之内。

为了后面讲解的方便，我统一用“考虑到下标 i 的元素为止，这些元素是否存在某个子集的元素之和为 j”来表示这个含义。

从这个状态的定义中我们可以看出，我们不是一下子就把数组里所有的物品都考虑进去，也不是一下子就去考虑某个子集之和是否等于 target = sum / 2 ，我们是从一个规模较小的问题出发，一个数一个数地去尝试，一点一点扩大考虑的子集的和的大小。这一点我们刚刚也提到过，这个思想是十分重要的。

动态规划的一个经典的思考路径就是这样的：从一个最小的问题出发，一点一点解决更大的问题，直到我们要解决的那个规模的问题，这是自底向上的“动态规划”的思路。在求解的过程中，记录求解的过程，在更大规模问题的求解上，我们不是直接求解，而是直接去查已经求得的规模较小的问题的解，这也是动态规划的一个特点：“最优子结构”。

（2）状态转移方程

思考状态转移方程，很多时候其实就是在做分类讨论，“0-1 背包问题”分类讨论的标准其实也是很常见的，就是我们在一个一个尝试物品的时候，当前考虑的这个物品选与不选，就能得到这个状态转移方程。

① 如果不选下标为 i 的元素，dp[i][j] 的值就完全取决于 dp[i - 1][j]

dp[i][j] = dp[i - 1][j]

② 如果选择下标为 i 的元素，依然要进行分类讨论：

如果下标为 i 的元素的值，恰好等于 j，那么我可以单独把 nums[i] 当做一个子集，直接将 dp[i][j] = true；
如若不然，dp[i][j] 就要看，之前的那些数里面，即下标为 [0, i - 1] 的这些数里面，是否能够找到和为 [j - nums[i]] 的一些数。写成等式是这样的：

dp[i][j] = (nums[i] == j) or dp[i - 1][j - nums[i]] (j - nums[i] > 0)

因此我们融合一下上面的两种情况：

dp[i][j] = dp[i - 1][j] or (nums[i] == j) or dp[i - 1][j - nums[i]] (j - nums[i] > 0)

我们再解释一下这个等式：（希望我解释到这里，大家不要被我搞晕了。）

（3）考虑初始化

dp[0][0] = false

（4）考虑输出

dp[len - 1][target]

下面我们编写代码：

1、首先把数组的长度赋值给一个变量 len，由于题目已经说了数组非空，因此不需要对数组长度是否为 0 做一个特判；

2、由于我们就是要找背包容量为 sum / 2 的子集，因此 sum 得先计算一下，并且再做一个特判，如果 sum / 2 是奇数，刚才我们已经分析过了，一定找不到这种分割，直接返回 false；

3、接下来就是我们动态规划填表格的过程了，创建一个长为 len ，宽为 target + 1 的表格，为什么要加 1 呢，这是因为容量为 0 也是我们需要考虑的一个状态。

是一个布尔数组。

4、先填写第 1 行，即只考虑下标为 0 的那个元素，很显然，它只能填满容量为它自己的那个背包，因此，我们可以直接写

dp[0][nums[0]] = true;

但是写成这样，要注意 nums[0] 有可能会越界，因此，能这样写的前提是 nums[0] <= target

5、接下来，我们用两个 for 循环来填写下面的表格

（1）因为第 1 个元素我们已经考虑过了，因此，我们从第 2 个元素，也就是下标为 1 的元素开始考虑，第 2 维从容积为 0 直到容积为 target。

（2）根据状态转移方程

如果当前考虑的这个数 nums[i] 很大，大到超过了 j，那么
dp[i][j] 至少是 dp[i - 1][j] 的值

如果 nums[i] 恰好是 j ，直接给 dp[i][j] 赋值为 true，否则，接下来就应该考虑在 nums[i] 严格小于 j 的时候，nums[i] 就有选和不选两种情况，

如果不选，直接参考 dp[i - 1][j] 的值，
如果选，就应该看到 下标 i - 1 为止，是否能凑出和为 j - nums[i] 的子集。

dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]

最后，根据刚才的分析，两层 for 循环就填完了这张表格，我们返回的就是 dp[len - 1][target]。

这是我们第 1 版的代码，提交到力扣的评测系统以后，能够得到一个通过。

在这里我们对几个细节进行优化：

1、由于 or

逻辑运算具有短路的特性，因此，其实只要在填表的过程中发现某一格是 true，它正下面的所有的格都是 true。特别地，如果某一行的最后一格的值是 true，下面所有的行的最后一个就一定是 true，输出的那个状态就一定为 true，因此在每一行填完以后，可以做一个判断，如果最后一格为 true，整个方法就可以直接返回。

2、注意到 dp[i - 1][j - nums[i]] 这个表达式，它虽然是在 nums[i] < j 的情况下成立的，但是当 j == nums[i] 的时候，我们其实讨论过，单独的 nums[i] 就可以构成和为 j 的子集，因此将 dp[i - 1][0] 设置成 true 是完全合理的，请大家再仔细思考一下，第二维值为 0 的这个状态，它的值只会被之后的值所参考，当 nums[i] == j 的时候，dp[i][j] 参考 dp[i - 1][0] ，把它设置为 true 虽然不符合语义，但是从结果上看是完全合理的。

这样写的代码可以少做一次判断。

我们再提交一版代码是可以通过的。

---

对于 0-1 背包问题有经验的朋友一定知道，其实解决这个问题，在空间上还以进行压缩。

因为我们在当前行总是参考了它上一行以及它上一行左边的值，不会在参考到之前的行的值，因此我们在填表的过程中只需要保留 2 行即可，这可以使用“滚动数组”的编码技巧实现。这里作为练习留给大家实现。

更特别的是，我们还可以将状态数组设置为 1 行，那么在更新值得时候，我们从后向前更新。

那么为什么不能从前向后更新呢？依然是模拟之前填表的过程，如果从前向后更新，新状态的值会参考到这一行的新状态，但事实上，我们需要的是上一行的旧状态。

但是如果从后向前更新就不存在这个问题了，因为考虑之前的状态值，之前的状态一定没有被更新过。如果想不明白这一点的朋友，不妨再熟悉一下动态规划填表格的这个过程，相信不难理解。

这个技巧是一个经验的总结，如果没有想到也没有关系，把这个技巧当做一个知识点进行学习，在以后遇到类似的问题的时候，能够灵活应用即可。

下面我们看一下代码：

参考资料：

1、https://blog.csdn.net/qq_37767455/article/details/99086678