LC 416. 分割等和子集

题目描述

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

给你一个只包含正整数的非空数组 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]$ 代表考虑前 $i$ 个数值，其选择数字总和不超过 $j$ 的最大价值。

转移方程：

/image_1.png)

但题目并不是问我们「最大价值是多少」，而是问「是否能凑出最大价值」。

因此我们可以对 01 背包的状态定义进行修改，使其直接与我们答案相关联：

$f[i][j]$ 代表考虑前 $i$ 个数值，其选择数字总和是否恰好为 $j$。

此时 $dp$ 数组中存储的是「布尔类型」的动规值。

相应的状态转移方程调整为：

/image_2.png)

$∨$ 代表逻辑「或」的意思。

新转移方程代表的意思为：想要 $f[i][j]$ (考虑前 $i$ 个数值，选择的数字总和恰好为 $j$ ) 为真。需要满足以下两种方案，至少一种为 $true$：

1. $f[i-1][j]$ (不选第 $i$ 件物品，选择的数字总和恰好为 $j$ ) 为 $true$

2. $f[i-1][j-nums[i]]$ (选第 $i$ 件物品，选择的数字总和恰好为 $j$ ) 为 $true$

至此，我们利用 01 背包的基本思想，修改了「状态定义」，使其与答案直接相关联，然后根据新的「状态定义」调整了我们的「转移方程」。

但还没结束。

当我们与某个模型的「状态定义」进行了修改之后，除了考虑调整「转移方程」以外，还需要考虑修改「初始化」状态。

试考虑，我们创建的 $dp$ 数组存储的是布尔类型，初始值都是 $false$，这意味着无论我们怎么转移下去，都不可能产生一个 $true$，最终所有的状态都仍然是 $false$。

换句话说，我们还需要一个有效值 $true$ 来帮助整个过程能递推下去。

通常我们使用「首行」来初始化「有效值」。

对于本题，显然我们可以通过「先处理第一个物品」来得到「有效值」，即令 $f[0][nums[0]] = true$。

$f[0][nums[0]] = true$ 代表只有容量为 $nums[0]$ 的背包才符合「恰好」的要求。

但我们无法确保 $nums[0]$ 不会超过我们的「最大背包」容量（也就是第一个物品过大，永远无法装入背包的情况）。

因此我们要通过处理下一行来得到有效值？或是先给物品排个序？

事实上，这里有一个技巧，就是我们增加一个「不考虑任何物品」的情况讨论。

之前我们的状态定义是 $f[i][j]$ 代表考虑下标为 $i$ 之前的所有物品。现在我们可以加入不考虑任何物品的情况，也就是将「物品编号」从 0 开始调整为从 1 开始。

举个🌰，原本我们的 $f[0][x]$ 代表只考虑第一件物品、$f[1][x]$ 代表考虑第一件和第二件物品；调整后我们的 $f[0][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];
    }
}

时间复杂度：$target$ 为数组总和的一半，$n$ 数组元素个数。为共有 $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];
    }
}

时间复杂度：$target$ 为数组总和的一半，$n$ 数组元素个数。为共有 $n target$ 个状态需要被转移，复杂度为 $O(n 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];
    }
}

时间复杂度：$target$ 为数组总和的一半，$n$ 数组元素个数。为共有 $n target$ 个状态需要被转移，复杂度为 $O(n target)$
空间复杂度：$O(target)$

总结

今天我们又做了一遍「416. 分割等和子集」，但却是以另外一个角度进行求解：

通过修改 01 背包的「状态定义」和「转移方程」实现「直接求解」。

但这样的做法属于特题特解吗？

其实不属于。反而这是「背包问题」中一个可推广的性质：

我们可以通过将一个背包问题的「状态定义」从最多不超过 XX 容量修改为背包容量恰好为 XX，同时再把「有效值构造」出来，也即是将物品下标调整为从 1 开始，设置 $dp[0][0]$ 为初始值。

这其实是另外一类「背包问题」，它不对应「价值最大化」，对应的是「能否取得最大/特定价值」。这样的「背包问题」同样具有普遍性。

需要大家进行掌握 ~

最后

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

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

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

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

背包 DP

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

LC 416. 分割等和子集上一篇

LC 1006. 笨阶乘下一篇