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