经典动态规划：子集背包问题
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 416. Partition Equal Subset Sum | 416. 分割等和子集 | 🟠 |
| - | 剑指 Offer II 101. 分割等和子集 | 🟢 |
———–
上篇文章 经典动态规划：0-1 背包问题 详解了通用的 0-1 背包问题，今天来看看背包问题的思想能够如何运用到其他算法题目。
而且，不是经常有读者问，怎么将二维动态规划压缩成一维动态规划吗？这就是空间压缩，很容易的，本文也会提及这种技巧。
读者在阅读本文之前务必读懂前文 经典动态规划：0-1 背包问题 中讲的套路，因为本文就是按照背包问题的解题模板来讲解的。
一、问题分析
看一下力扣第 416 题「 分割等和子集」：
输入一个只包含正整数的非空数组 nums，请你写一个算法，判断这个数组是否可以被分割成两个子集，使得两个子集的元素和相等。
算法的函数签名如下：
// 输入一个集合，返回是否能够分割成和相等的两个子集
boolean canPartition(int[] nums);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 输入一个集合，返回是否能够分割成和相等的两个子集
bool canPartition(vector<int>& nums);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
# 输入一个集合，返回是否能够分割成和相等的两个子集
def canPartition(nums: List[int]) -> bool:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 输入一个集合，返回是否能够分割成和相等的两个子集
func canPartition(nums []int) bool {}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 输入一个集合，返回是否能够分割成和相等的两个子集
var canPartition = function(nums) {};
比如说输入 nums = [1,5,11,5]，算法返回 true，因为 nums 可以分割成 [1,5,5] 和 [11] 这两个子集。
如果说输入 nums = [1,3,2,5]，算法返回 false，因为 nums 无论如何都不能分割成两个和相等的子集。
对于这个问题，看起来和背包没有任何关系，为什么说它是背包问题呢？
首先回忆一下背包问题大致的描述是什么：
给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？
那么对于这个问题，我们可以先对集合求和，得出 sum，把问题转化为背包问题：
给一个可装载重量为 sum / 2 的背包和 N 个物品，每个物品的重量为 nums[i]。现在让你装物品，是否存在一种装法，能够恰好将背包装满？
你看，这就是背包问题的模型，甚至比我们之前的经典背包问题还要简单一些，下面我们就直接转换成背包问题，开始套前文讲过的背包问题框架即可。
二、解法分析
第一步要明确两点，「状态」和「选择」。
这个前文 经典动态规划：背包问题 已经详细解释过了，状态就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。
第二步要明确 dp 数组的定义。
按照背包问题的套路，可以给出如下定义：
dp[i][j] = x 表示，对于前 i 个物品（i 从 1 开始计数），当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。
比如说，如果 dp[4][9] = true，其含义为：对于容量为 9 的背包，若只是在前 4 个物品中进行选择，可以有一种方法把背包恰好装满。
或者说对于本题，含义是对于给定的集合中，若只在前 4 个数字中进行选择，存在一个子集的和可以恰好凑出 9。
根据这个定义，我们想求的最终答案就是 dp[N][sum/2]，base case 就是 dp[..][0] = true 和 dp[0][..] = false，因为背包没有空间的时候，就相当于装满了，而当没有物品可选择的时候，肯定没办法装满背包。
第三步，根据「选择」，思考状态转移的逻辑。
回想刚才的 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态 dp[i-1][j]，继承之前的结果。
如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么是否能够恰好装满背包，取决于状态 dp[i-1][j-nums[i-1]]。
由于 dp 数组定义中的 i 是从 1 开始计数，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]，这一点不要搞混。
dp[i - 1][j-nums[i-1]] 也很好理解：你如果装了第 i 个物品，就要看背包的剩余重量 j - nums[i-1] 限制下是否能够被恰好装满。
换句话说，如果 j - nums[i-1] 的重量可以被恰好装满，那么只要把第 i 个物品装进去，也可恰好装满 j 的重量；否则的话，重量 j 肯定是装不满的。
最后一步，把伪码翻译成代码，处理一些边界情况。
以下是我的 Java 代码，完全翻译了之前的思路，并处理了一些边界情况：
boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) sum += num;
// 和为奇数时，不可能划分成两个和相等的集合
if (sum % 2 != 0) return false;
int n = nums.length;
sum = sum / 2;
boolean[][] dp = new boolean[n + 1][sum + 1];
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][sum];
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int num : nums) sum += num;
// 和为奇数时，不可能划分成两个和相等的集合
if (sum % 2 != 0) return false;
int n = nums.size();
sum = sum / 2;
vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1));
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][sum];
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def canPartition(nums: List[int]) -> bool:
sum = 0
for num in nums: # 遍历计算数组总和
sum += num
# 和为奇数时，不可能划分成两个和相等的集合
if sum % 2 != 0:
return False
n = len(nums)
sum = sum // 2
# 定义二维数组 dp
dp = [[False] * (sum + 1) for _ in range(n + 1)]
# base case
for i in range(n + 1):
dp[i][0] = True
for i in range(1, n + 1):
for j in range(1, sum + 1):
if j - nums[i - 1] < 0:
# 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j]
else:
# 装入或不装入背包
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
return dp[n][sum]
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func canPartition(nums []int) bool {
sum := 0
for _, num := range nums {
sum += num
}
// 和为奇数时，不可能划分成两个和相等的集合
if sum % 2 != 0 {
return false
}
n := len(nums)
sum = sum / 2
dp := make([][]bool, n + 1)
// base case
for i := 0; i <= n; i++ {
dp[i] = make([]bool, sum + 1)
dp[i][0] = true
}
for i := 1; i <= n; i++ {
for j := 1; j <= sum; j++ {
if j - nums[i - 1] < 0 {
// 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j]
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
}
}
}
return dp[n][sum]
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var canPartition = function(nums) {
var sum = 0;
for (var num of nums) sum += num;
// 和为奇数时，不可能划分成两个和相等的集合
if (sum % 2 !== 0) return false;
var n = nums.length;
sum = sum / 2;
var dp = new Array(n + 1).fill(false).map(() => new Array(sum + 1).fill(false));
// base case
for (var i = 0; i <= n; i++){
dp[i][0] = true;
}
for (var i = 1; i <= n; i++) {
for (var j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][sum];
};
三、进一步优化
再进一步，是否可以优化这个代码呢？注意到 dp[i][j] 都是通过上一行 dp[i-1][..] 转移过来的，之前的数据都不会再使用了。
所以，我们可以参照前文
对动态规划进行降维打击，将二维 dp 数组压缩为一维，节约空间复杂度：
boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) sum += num;
// 和为奇数时，不可能划分成两个和相等的集合
if (sum % 2 != 0) return false;
int n = nums.length;
sum = sum / 2;
boolean[] dp = new boolean[sum + 1];
// base case
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = sum; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[sum];
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int num : nums) sum += num;
// 和为奇数时，不可能划分成两个和相等的集合
if (sum % 2 != 0) return false;
int n = nums.size();
sum = sum / 2;
vector<bool> dp(sum + 1, false);
// base case
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = sum; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[sum];
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def canPartition(nums: List[int]) -> bool:
sum = 0
for num in nums:
sum += num
# 和为奇数时，不可能划分成两个和相等的集合
if sum % 2 != 0:
return False
n = len(nums)
sum = sum // 2
dp = [False] * (sum + 1)
# base case
dp[0] = True
for i in range(n):
for j in range(sum, -1, -1):
if j - nums[i] >= 0:
dp[j] = dp[j] or dp[j - nums[i]]
return dp[sum]
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func canPartition(nums []int) bool {
sum := 0
for _, num := range nums {
sum += num
}
// 和为奇数时，不可能划分成两个和相等的集合
if sum % 2 != 0 {
return false
}
n := len(nums)
sum = sum / 2
dp := make([]bool, sum + 1)
// base case
dp[0] = true
for i := 0; i < n; i++ {
for j := sum; j >= 0; j-- {
if j - nums[i] >= 0 {
dp[j] = dp[j] || dp[j - nums[i]]
}
}
}
return dp[sum]
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var canPartition = function(nums) {
let sum = 0;
for (let num of nums) sum += num;
// 和为奇数时，不可能划分成两个和相等的集合
if (sum % 2 !== 0) return false;
let n = nums.length;
sum = sum / 2;
let dp = new Array(sum + 1).fill(false);
// base case
dp[0] = true;
for (let i = 0; i < n; i++) {
for (let j = sum; j >= 0; j--) {
if (j - nums[i] >= 0) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
}
return dp[sum];
};
其实这段代码和之前的解法思路完全相同，只在一行 dp 数组上操作，i 每进行一轮迭代，dp[j] 其实就相当于 dp[i-1][j]，所以只需要一维数组就够用了。
唯一需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。
至此，子集切割的问题就完全解决了，时间复杂度 O(n\*sum)，空间复杂度 O(sum)。
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释