题目描述
这是 LeetCode 上的 416. 分割等和子集 ，难度为 中等。
Tag : 「背包 DP」
给你一个 只包含正整数 的 非空 数组 nums 。
请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 复制代码
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。 复制代码
提示：
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 100
基本分析
基本的「将原问题抽象为 01 背包问题」的分析在 上一讲 讲过啦 ~
本节要解决的问题是：如何将「间接求解」的方式转为「直接求解」，并学习为什么能这么做，此类做法是否有共性 ...
直接求解
我们先来回顾一下 上一节 使用的「状态定义」和「转移方程」。
状态定义：
f[i][j]f[i][j] 代表考虑前 ii 个数值，其选择数字总和不超过 jj 的最大价值。
转移方程：
但题目并不是问我们「最大价值是多少」，而是问「是否能凑出最大价值」。
因此我们可以对 01 背包的状态定义进行修改，使其直接与我们答案相关联：
f[i][j]f[i][j] 代表考虑前 ii 个数值，其选择数字总和是否恰好为 jj。
此时 dpdp 数组中存储的是「布尔类型」的动规值。
相应的状态转移方程调整为：
∨∨ 代表逻辑「或」的意思。
新转移方程代表的意思为：想要 f[i][j]f[i][j] (考虑前 ii 个数值，选择的数字总和恰好为 jj ) 为真。需要满足以下两种方案，至少一种为 truetrue：
1. f[i-1][j]f[i−1][j] (不选第 ii 件物品，选择的数字总和恰好为 jj ) 为 truetrue
2. f[i-1][j-nums[i]]f[i−1][j−nums[i]] (选第 ii 件物品，选择的数字总和恰好为 jj ) 为 truetrue
至此，我们利用 01 背包的基本思想，修改了「状态定义」，使其与答案直接相关联，然后根据新的「状态定义」调整了我们的「转移方程」。
但还没结束。
当我们与某个模型的「状态定义」进行了修改之后，除了考虑调整「转移方程」以外，还需要考虑修改「初始化」状态。
试考虑，我们创建的 dpdp 数组存储的是布尔类型，初始值都是 falsefalse，这意味着无论我们怎么转移下去，都不可能产生一个 truetrue，最终所有的状态都仍然是 falsefalse。
换句话说，我们还需要一个有效值 truetrue 来帮助整个过程能递推下去。
通常我们使用「首行」来初始化「有效值」。
对于本题，显然我们可以通过「先处理第一个物品」来得到「有效值」，即令 f[0][nums[0]] = truef[0][nums[0]]=true。
f[0][nums[0]] = truef[0][nums[0]]=true 代表只有容量为 nums[0]nums[0] 的背包才符合「恰好」的要求。
但我们无法确保 nums[0]nums[0] 不会超过我们的「最大背包」容量（也就是第一个物品过大，永远无法装入背包的情况）。
因此我们要通过处理下一行来得到有效值？或是先给物品排个序？
事实上，这里有一个技巧，就是我们增加一个「不考虑任何物品」的情况讨论。
之前我们的状态定义是 f[i][j]f[i][j] 代表考虑下标为 ii 之前的所有物品。现在我们可以加入不考虑任何物品的情况，也就是将「物品编号」从 0 开始调整为从 1 开始。
举个🌰，原本我们的 f[0][x]f[0][x] 代表只考虑第一件物品、f[1][x]f[1][x] 代表考虑第一件和第二件物品；调整后我们的 f[0][x]f[0][x] 代表不考虑任何物品、f[1][x]f[1][x] 代表只考虑第一件物品 ...
这种技巧本质上还是利用了「哨兵」的思想。
有了以上的分析思路，和 上一讲 的代码基础之后，我们可以很容易写出代码。
虽然更换了状态定义和转移方程，但仍然有「常规解法」、「滚动数组优化」「一维空间优化」几种实现方法。我们快速过一下 ~
常规解法
代码：
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; //「等和子集」的和必然是总和的一半 int sum = 0; for (int i : nums) sum += i; int target = sum / 2; // 对应了总和为奇数的情况，注定不能被分为两个「等和子集」 if (target * 2 != sum) return false; // f[i][j] 代表考虑前 i 件物品，能否凑出价值「恰好」为 j 的方案 boolean[][] f = new boolean[n+1][target+1]; f[0][0] = true; for (int i = 1; i <= n; i++) { int t = nums[i-1]; for (int j = 0; j <= target; j++) { // 不选该物品 boolean no = f[i-1][j]; // 选该物品 boolean yes = j >= t ? f[i-1][j-t] : false; f[i][j] = no | yes; } } return f[n][target]; } } 复制代码
- 时间复杂度：targettarget 为数组总和的一半，nn 数组元素个数。为共有 n * targetn∗target 个状态需要被转移，复杂度为 O(n * target)O(n∗target)
- 空间复杂度：O(n * target)O(n∗target)
「滚动数组」解法
代码：
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; //「等和子集」的和必然是总和的一半 int sum = 0; for (int i : nums) sum += i; int target = sum / 2; // 对应了总和为奇数的情况，注定不能被分为两个「等和子集」 if (target * 2 != sum) return false; // f[i][j] 代表考虑前 i 件物品，能否凑出价值「恰好」为 j 的方案 // 修改「物品维度」为 2 boolean[][] f = new boolean[2][target+1]; f[0][0] = true; for (int i = 1; i <= n; i++) { int t = nums[i-1]; for (int j = 0; j <= target; j++) { // 不选该物品 boolean no = f[(i-1)&1][j]; // 选该物品 boolean yes = j >= t ? f[(i-1)&1][j-t] : false; f[i&1][j] = no | yes; } } return f[n&1][target]; } } 复制代码
- 时间复杂度：targettarget 为数组总和的一半，nn 数组元素个数。为共有 n * targetn∗target 个状态需要被转移，复杂度为 O(n * target)O(n∗target)
- 空间复杂度：O(target)O(target)
「一维空间优化」解法
代码：
class Solution { public boolean canPartition(int[] nums) { int n = nums.length; //「等和子集」的和必然是总和的一半 int sum = 0; for (int i : nums) sum += i; int target = sum / 2; // 对应了总和为奇数的情况，注定不能被分为两个「等和子集」 if (target * 2 != sum) return false; // 取消「物品维度」 boolean[] f = new boolean[target+1]; f[0] = true; for (int i = 1; i <= n; i++) { int t = nums[i-1]; for (int j = target; j >= 0; j--) { // 不选该物品 boolean no = f[j]; // 选该物品 boolean yes = j >= t ? f[j-t] : false; f[j] = no | yes; } } return f[target]; } } 复制代码
- 时间复杂度：targettarget 为数组总和的一半，nn 数组元素个数。为共有 n * targetn∗target 个状态需要被转移，复杂度为 O(n * target)O(n∗target)
- 空间复杂度：O(target)O(target)
总结
今天我们又做了一遍「416. 分割等和子集」，但却是以另外一个角度进行求解：
通过修改 01 背包的「状态定义」和「转移方程」实现「直接求解」。
但这样的做法属于特题特解吗？
其实不属于。反而这是「背包问题」中一个可推广的性质：
我们可以通过将一个背包问题的「状态定义」从最多不超过 XX 容量修改为背包容量恰好为 XX，同时再把「有效值构造」出来，也即是将物品下标调整为从 1 开始，设置 dp[0][0]dp[0][0] 为初始值。
这其实是另外一类「背包问题」，它不对应「价值最大化」，对应的是「能否取得最大/特定价值」。这样的「背包问题」同样具有普遍性。
需要大家进行掌握 ~
最后
这是我们「刷穿 LeetCode」系列文章的第 No.416 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
