第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0416. 分割等和子集

题目地址(416. 分割等和子集)

https://leetcode-cn.com/problems/partition-equal-subset-sum/

题目描述

1
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
2
3
注意:
4
5
每个数组中的元素不会超过 100
6
数组的大小不会超过 200
7
示例 1:
8
9
输入: [1, 5, 11, 5]
10
11
输出: true
12
13
解释: 数组可以分割成 [1, 5, 5] 和 [11].
14
15
16
示例 2:
17
18
输入: [1, 2, 3, 5]
19
20
输出: false
21
22
解释: 数组不能分割成两个元素和相等的子集.
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

抽象能力不管是在工程还是算法中都占据着绝对重要的位置。比如上题我们可以抽象为:
给定一个非空数组,和是 sum,能否找到这样的一个子序列,使其和为 2/sum
我们做过二数和,三数和, 四数和,看到这种类似的题会不会舒适一点,思路更开阔一点。
老司机们看到转化后的题,会立马想到背包问题,这里会提供深度优先搜索背包两种解法。

深度优先遍历

我们再来看下题目描述,sum 有两种情况,
  1. 1.
    如果 sum % 2 === 1, 则肯定无解,因为 sum/2 为小数,而数组全由整数构成,子数组和不可能为小数。
  2. 2.
    如果 sum % 2 === 0, 需要找到和为 2/sum 的子序列 针对 2,我们要在 nums 里找到满足条件的子序列 subNums。 这个过程可以类比为在一个大篮子里面有 N 个球,每个球代表不同的数字,我们用一小篮子去抓取球,使得拿到的球数字和为 2/sum。那么很自然的一个想法就是,对大篮子里面的每一个球,我们考虑取它或者不取它,如果我们足够耐心,最后肯定能穷举所有的情况,判断是否有解。上述思维表述为伪代码如下:
1
令 target = sum / 2, nums 为输入数组, cur 为当前当前要选择的数字的索引
2
nums 为输入数组,target为当前求和目标,cur为当前判断的数
3
function dfs(nums, target, cur)
4
如果target < 0 或者 cur > nums.length
5
return false
6
否则
7
如果 target = 0, 说明找到答案了,返回true
8
否则
9
取当前数或者不取,进入递归 dfs(nums, target - nums[cur], cur + 1) || dfs(nums, target, cur + 1)
Copied!
因为对每个数都考虑取不取,所以这里时间复杂度是 O(2 ^ n), 其中 n 是 nums 数组长度,
javascript 实现
1
var canPartition = function (nums) {
2
let sum = nums.reduce((acc, num) => acc + num, 0);
3
if (sum % 2) {
4
return false;
5
}
6
sum = sum / 2;
7
return dfs(nums, sum, 0);
8
};
9
10
function dfs(nums, target, cur) {
11
if (target < 0 || cur > nums.length) {
12
return false;
13
}
14
return (
15
target === 0 ||
16
dfs(nums, target - nums[cur], cur + 1) ||
17
dfs(nums, target, cur + 1)
18
);
19
}
Copied!
不出所料,这里是超时了,我们看看有没优化空间
  1. 1.
    如果 nums 中最大值 > 2/sum, 那么肯定无解
  2. 2.
    在搜索过程中,我们对每个数都是取或者不取,并且数组中所有项都为正数。我们设取的数和为 pickedSum,不难得 pickedSum <= 2/sum, 同时要求丢弃的数为 discardSum,不难得 pickedSum <= 2 / sum。
我们同时引入这两个约束条件加强剪枝:
优化后的代码如下
1
var canPartition = function (nums) {
2
let sum = nums.reduce((acc, num) => acc + num, 0);
3
if (sum % 2) {
4
return false;
5
}
6
sum = sum / 2;
7
nums = nums.sort((a, b) => b - a);
8
if (sum < nums[0]) {
9
return false;
10
}
11
return dfs(nums, sum, sum, 0);
12
};
13
14
function dfs(nums, pickRemain, discardRemain, cur) {
15
if (pickRemain === 0 || discardRemain === 0) {
16
return true;
17
}
18
19
if (pickRemain < 0 || discardRemain < 0 || cur > nums.length) {
20
return false;
21
}
22
23
return (
24
dfs(nums, pickRemain - nums[cur], discardRemain, cur + 1) ||
25
dfs(nums, pickRemain, discardRemain - nums[cur], cur + 1)
26
);
27
}
Copied!
leetcode 是 AC 了,但是时间复杂度 O(2 ^ n), 算法时间复杂度很差,我们看看有没更好的。

DP 解法

在用 DFS 是时候,我们是不关心取数的规律的,只要保证接下来要取的数在之前没有被取过即可。那如果我们有规律去安排取数策略的时候会怎么样呢,比如第一次取数安排在第一位,第二位取数安排在第二位,在判断第 i 位是取数的时候,我们是已经知道前 i-1 个数每次是否取的所有子序列组合,记集合 S 为这个子序列的和。再看第 i 位取数的情况, 有两种情况取或者不取
  1. 1.
    取的情况,如果 target-nums[i]在集合 S 内,则返回 true,说明前 i 个数能找到和为 target 的序列
  2. 2.
    不取的情况,如果 target 在集合 S 内,则返回 true,否则返回 false
也就是说,前 i 个数能否构成和为 target 的子序列取决为前 i-1 数的情况。
记 F[i, target] 为 nums 数组内前 i 个数能否构成和为 target 的子序列的可能,则状态转移方程为
F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]]
状态转移方程出来了,代码就很好写了,DFS + DP 都可以解,有不清晰的可以参考下 递归和动态规划, 这里只提供 DP 解法
伪代码表示
1
n = nums.length
2
target 为 nums 各数之和
3
如果target不能被2整除,
4
返回false
5
6
令dp为n * target 的二维矩阵, 并初始为false
7
遍历0:n, dp[i][0] = true 表示前i个数组成和为0的可能
8
9
遍历 0 到 n
10
遍历 0 到 target
11
if 当前值j大于nums[i]
12
dp[i + 1][j] = dp[i][j-nums[i]] || dp[i][j]
13
else
14
dp[i+1][j] = dp[i][j]
Copied!
算法时间复杂度 O(n*m), 空间复杂度 O(n*m), m 为 sum(nums) / 2
javascript 实现
1
var canPartition = function (nums) {
2
let sum = nums.reduce((acc, num) => acc + num, 0);
3
if (sum % 2) {
4
return false;
5
} else {
6
sum = sum / 2;
7
}
8
9
const dp = Array.from(nums).map(() =>
10
Array.from({ length: sum + 1 }).fill(false)
11
);
12
13
for (let i = 0; i < nums.length; i++) {
14
dp[i][0] = true;
15
}
16
17
for (let i = 0; i < dp.length - 1; i++) {
18
for (let j = 0; j < dp[0].length; j++) {
19
dp[i + 1][j] =
20
j - nums[i] >= 0 ? dp[i][j] || dp[i][j - nums[i]] : dp[i][j];
21
}
22
}
23
24
return dp[nums.length - 1][sum];
25
};
Copied!
再看看有没有优化空间,看状态转移方程 F[i, target] = F[i - 1, target] || F[i - 1, target - nums[i]] 第 n 行的状态只依赖于第 n-1 行的状态,也就是说我们可以把二维空间压缩成一维
伪代码
1
遍历 0 到 n
2
遍历 j 从 target 到 0
3
if 当前值j大于nums[i]
4
dp[j] = dp[j-nums[i]] || dp[j]
5
else
6
dp[j] = dp[j]
Copied!
时间复杂度 O(n*m), 空间复杂度 O(n) javascript 实现
1
var canPartition = function (nums) {
2
let sum = nums.reduce((acc, num) => acc + num, 0);
3
if (sum % 2) {
4
return false;
5
}
6
sum = sum / 2;
7
const dp = Array.from({ length: sum + 1 }).fill(false);
8
dp[0] = true;
9
10
for (let i = 0; i < nums.length; i++) {
11
for (let j = sum; j > 0; j--) {
12
dp[j] = dp[j] || (j - nums[i] >= 0 && dp[j - nums[i]]);
13
}
14
}
15
16
return dp[sum];
17
};
Copied!
其实这道题和 leetcode 518 是换皮题,它们都可以归属于背包问题

背包问题

背包问题描述

有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci,得到的 价值是 Wi。求解将哪些物品装入背包可使价值总和最大。
背包问题的特性是,每种物品,我们都可以选择放或者不放。令 F[i, v]表示前 i 件物品放入到容量为 v 的背包的状态。
针对上述背包,F[i, v]表示能得到最大价值,那么状态转移方程为
1
F[i, v] = max{F[i-1, v], F[i-1, v-Ci] + Wi}
Copied!
针对 416. 分割等和子集这题,F[i, v]的状态含义就表示前 i 个数能组成和为 v 的可能,状态转移方程为
1
F[i, v] = F[i-1, v] || F[i-1, v-Ci]
Copied!
再回过头来看下leetcode 518, 原题如下
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
带入背包思想,F[i,v] 表示用前 i 种硬币能兑换金额数为 v 的组合数,状态转移方程为 F[i, v] = F[i-1, v] + F[i-1, v-Ci]
javascript 实现
1
/**
2
* @param {number} amount
3
* @param {number[]} coins
4
* @return {number}
5
*/
6
var change = function (amount, coins) {
7
const dp = Array.from({ length: amount + 1 }).fill(0);
8
dp[0] = 1;
9
for (let i = 0; i < coins.length; i++) {
10
for (let j = 1; j <= amount; j++) {
11
dp[j] = dp[j] + (j - coins[i] >= 0 ? dp[j - coins[i]] : 0);
12
}
13
}
14
return dp[amount];
15
};
Copied!
注意这里内层循环和外层循环不能颠倒,即必须外层是遍历 coins,内层遍历 amount,否则 coins 就可能被使用多次而导致和题意不符
复杂度分析
  • 时间复杂度:$O(amount * len(coins))$
  • 空间复杂度:$O(amount)$

参考

  • 背包九讲 基本上看完前四讲就差不多够刷题了。
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。