LC 416. 分割等和子集

题目描述

这是 LeetCode 上的 416. 分割等和子集(上) ，难度为 中等。

给你一个 只包含正整数 的 非空 数组 nums 。

请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

1
2
3
4
5
输入：nums = [1,5,11,5]

输出：true

解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
1
2
3
4
5
输入：nums = [1,2,3,5]

输出：false

解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

前言

今天是我们讲解动态规划专题中的 「背包问题」的第二天。

在众多背包问题中「01 背包问题」是最为核心的，因此我建议你先精读过 背包问题 第一讲 之后再阅读本文。

另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。

背包问题我会按照编排好的顺序进行讲解（每 2~3 天更新一篇，确保大家消化）。

你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~

基本分析

通常「背包问题」相关的题，都是在考察我们的「建模」能力，也就是将问题转换为「背包问题」的能力。

由于本题是问我们能否将一个数组分成两个「等和」子集。

问题等效于能否从数组中挑选若干个元素，使得元素总和等于所有元素总和的一半。

这道题如果抽象成「背包问题」的话，应该是：

我们背包容量为 $target=sum/2$，每个数组元素的「价值」与「成本」都是其数值大小，求我们能否装满背包。

转换为 01 背包

由于每个数字（数组元素）只能被选一次，而且每个数字选择与否对应了「价值」和「成本」，求解的问题也与「最大价值」相关。

可以使用「01 背包」的模型来做。

当我们确定一个问题可以转化为「01 背包」之后，就可以直接套用「01 背包」的状态定义进行求解了。

注意，我们积累 DP 模型的意义，就是在于我们可以快速得到可靠的「状态定义」。

在 路径问题 中我教过你通用的 DP 技巧解法，但那是基于我们完全没见过那样的题型才去用的，而对于一些我们见过题型的 DP 题目，我们应该直接套用（或微调）该模型「状态定义」来做。

我们直接套用「01 背包」的状态定义：

$f[i][j]$ 代表考虑前 $i$ 个数值，其选择数字总和不超过 $j$ 的最大价值。

当有了「状态定义」之后，结合我们的「最后一步分析法」，每个数字都有「选」和「不选」两种选择。

因此不难得出状态转移方程：

image.png/image_0.png)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;

        int[][] f = new int[n][target + 1];
        // 先处理考虑第 1 件物品的情况
        for (int j = 0; j <= target; j++) {
            f[0][j] = j >= nums[0] ? nums[0] : 0;
        }

        // 再处理考虑其余物品的情况
        for (int i = 1; i < n; i++) {
            int t = nums[i];
            for (int j = 0; j <= target; j++) {
                // 不选第 i 件物品
                int no = f[i-1][j];
                // 选第 i 件物品
                int yes = j >= t ? f[i-1][j-t] + t : 0;
                f[i][j] = Math.max(no, yes);
            }
        }
        // 如果最大价值等于 target，说明可以拆分成两个「等和子集」
        return f[n-1][target] == target;
    }
}
  • 时间复杂度：$target$ 为数组总和的一半，$n$ 数组元素个数。为共有 $n target$ 个状态需要被转移，复杂度为 $O(n target)$
  • 空间复杂度：$O(n * target)$

「滚动数组」解法

在上一讲我们讲到过「01 背包」具有两种空间优化方式。

其中一种优化方式的编码实现十分固定，只需要固定的修改「物品维度」即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;

        // 将「物品维度」修改为 2
        int[][] f = new int[2][target + 1];
        // 先处理考虑第 1 件物品的情况
        for (int j = 0; j <= target; j++) {
            f[0][j] = j >= nums[0] ? nums[0] : 0;
        }

        // 再处理考虑其余物品的情况
        for (int i = 1; i < n; i++) {
            int t = nums[i];
            for (int j = 0; j <= target; j++) {
                // 不选第 i 件物品，将物品维度的使用加上「&1」
                int no = f[(i-1)&1][j];
                // 选第 i 件物品，将物品维度的使用加上「&1」
                int yes = j >= t ? f[(i-1)&1][j-t] + t : 0;
                f[i&1][j] = Math.max(no, yes);
            }
        }
        // 如果最大价值等于 target，说明可以拆分成两个「等和子集」
        // 将物品维度的使用加上「&1」
        return f[(n-1)&1][target] == target;
    }
}
  • 时间复杂度：$target$ 为数组总和的一半，$n$ 数组元素个数。为共有 $n target$ 个状态需要被转移，复杂度为 $O(n target)$
  • 空间复杂度：$O(target)$

「一维空间优化」解法

事实上，我们还能继续进行空间优化：只保留代表「剩余容量」的维度，同时将容量遍历方向修改为「从大到小」。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;

        // 将「物品维度」取消
        int[] f = new int[target + 1];
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            // 将「容量维度」改成从大到小遍历
            for (int j = target; j >= 0; j--) {
                // 不选第 i 件物品
                int no = f[j];
                // 选第 i 件物品
                int yes = j >= t ? f[j-t] + t : 0;
                f[j] = Math.max(no, yes);
            }
        }
        // 如果最大价值等于 target，说明可以拆分成两个「等和子集」
        return f[target] == target;
    }
}
  • 时间复杂度：$target$ 为数组总和的一半，$n$ 数组元素个数。为共有 $n target$ 个状态需要被转移，复杂度为 $O(n target)$
  • 空间复杂度：$O(target)$

总结

今天我们对昨天学的「01 背包」进行了应用。

可以发现，本题的难点在于对问题的抽象，主要考察的是如何将原问题转换为一个「01 背包」问题。

事实上，无论是 DP 还是图论，对于特定问题，大多都有相应的模型或算法。

难是难在如何将问题转化为我们的模型。

至于如何培养自己的「问题抽象能力」？

首先通常需要我们积累一定的刷题量，并对「转换问题的关键点」做总结。

例如本题，一个转换「01 背包问题」的关键点是我们需要将「划分等和子集」的问题等效于「在某个数组中选若干个数，使得其总和为某个特定值」的问题。

拓展

但这道题到这里还有一个”小问题“。

就是我们最后是通过「判断」来取得答案的。

通过判断取得的最大价值是否等于 $target$ 来决定是否能划分出「等和子集」。

虽然说逻辑上完全成立，但总给我们一种「间接求解」的感觉。

造成这种「间接求解」的感觉，主要是因为我们没有对「01 背包」的「状态定义」和「初始化」做任何改动。

但事实上，我们是可以利用「01 背包」的思想进行「直接求解」的。

因此在下一讲，我们还会再做一遍这道题。

不过却是以「另外一个角度」的「01 背包」思维来解决。

敬请期待 ~

最后

这是我们「刷穿 LeetCode」系列文章的第 No.416 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

背包 DP

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！