关注Java领域相关技术 记录有趣的事情

LeetCode-416. 分割等和子集

US-B.Ralph
US-B.Ralph
2020-10-112020-10-12

问题地址

LeetCode每日一题/2020-10-11

LeetCode416. 分割等和子集

问题描述

规则

  • 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

  • 每个数组中的元素不会超过 100
  • 数组的大小不会超过 200

示例

  • 示例1
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
  • 示例2
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

解析

解题思路

数据操作分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

public class LeetCode0416_PartitionEqualSubsetSum {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 0) return false;
        int sum = 0;
        int max = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            if (nums[i] > max) max = nums[i];
        }
        if ((sum & 1) == 1) return false;
        int target = sum / 2;
        if (max > target) return false;
        if (max == target) return true;

        boolean[][] ans = new boolean[len][target];
        for (int i = 0; i < len; i++) {
            ans[i][nums[i]] = true;
            if (i == 0) continue;

            if (ans[i - 1][target - nums[i]]) return true;
            for (int j = 0; j < target; j++) {
                if (ans[i - 1][j]) {
                    ans[i][j] = true;
                    if (j + nums[i] < target) ans[i][j + nums[i]] = true;
                }
            }
        }
        return false;
    }
}

官方解法

前言

  • 本题是经典的NP 完全问题，也就是说，如果你发现了该问题的一个多项式算法，那么恭喜你证明出了 P=NP，可以期待一下图灵奖了。
  • 正因如此，我们不应期望该问题有多项式时间复杂度的解法。我们能想到，例如基于贪心算法的「将数组降序排序后，依次将每个元素添加至当前元素和较小的子集中」之类的方法都是错误的，可以轻松地举出反例。因此，我们必须尝试非多项式时间复杂度的算法，例如时间复杂度与元素大小相关的动态规划。

方法一：动态规划

思路与算法：

  • 这道题可以换一种表述：给定一个只包含正整数的非空数组 \textit{nums}[0]，判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半。因此这个问题可以转换成「0−1 背包问题」。这道题与传统的「0−1 背包问题」的区别在于，传统的「0−1 背包问题」要求选取的物品的重量之和不能超过背包的总容量，这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。类似于传统的「0−1 背包问题」，可以使用动态规划求解。
  • 在使用动态规划求解之前，首先需要进行以下判断。
    • 根据数组的长度 n 判断数组是否可以被划分。如果 n\textit{target}，则除了 \textit{maxNum} 以外的所有元素之和一定小于 \textit{target}，因此不可能将数组分割成元素和相等的两个子集，直接返回 \text{false}。
  • 创建二维数组 \textit{dp}，包含 n 行 \textit{target}+1 列，其中 \textit{dp}[i][j] 表示从数组的 [0,i] 下标范围内选取若干个正整数（可以是 0 个），是否存在一种选取方案使得被选取的正整数的和等于 j。初始时，\textit{dp} 中的全部元素都是 \text{false}。
  • 在定义状态之后，需要考虑边界情况。以下两种情况都属于边界情况。
    • 如果不选取任何正整数，则被选取的正整数等于 0。因此对于所有 0 \le i 0 且 j>0 的情况，如何确定 \textit{dp}[i][j] 的值？需要分别考虑以下两种情况。
    • 如果 j \ge \textit{nums}[i]，则对于当前的数字 \textit{nums}[i]，可以选取也可以不选取，两种情况只要有一个为 \text{true}，就有 \textit{dp}[i][j]=\text{true}。
      • 如果不选取 \textit{nums}[i]，则 \textit{dp}[i][j]=\textit{dp}[i-1][j]；
      • 如果选取 \textit{nums}[i]，则 \textit{dp}[i][j]=\textit{dp}[i-1][j-\textit{nums}[i]]。
    • 如果 j<\textit{nums}[i]，则在选取的数字的和等于 j 的情况下无法选取当前的数字 \textit{nums}[i]，因此有 \textit{dp}[i][j]=\textit{dp}[i-1][j]。
  • 状态转移方程如下：

\textit{dp}[i][j]=\begin{cases} \textit{dp}[i-1][j]~|~\textit{dp}[i-1][j-\textit{nums}[i]],&j \ge \textit{nums}[i] \\ \textit{dp}[i-1][j],&j<\textit{nums}[i] \end{cases}

  • 最终得到 \textit{dp}[n-1][\textit{target}] 即为答案。
class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[][] dp = new boolean[n][target + 1];
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        dp[0][nums[0]] = true;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            for (int j = 1; j <= target; j++) {
                if (j >= num) {
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }
}
  • 上述代码的空间复杂度是 O(n \times \textit{target})。但是可以发现在计算 \textit{dp} 的过程中，每一行的 dp 值都只与上一行的 dp 值有关，因此只需要一个一维数组即可将空间复杂度降到 O(\textit{target})。此时的转移方程为：\textit{dp}[j]=\textit{dp}[j]\ |\ dp[j-\textit{nums}[i]]

  • 且需要注意的是第二层的循环我们需要从大到小计算，因为如果我们从小到大更新 \textit{dp} 值，那么在计算 \textit{dp}[j]dp[j] 值的时候，\textit{dp}[j-\textit{nums}[i]] 已经是被更新过的状态，不再是上一行的 \textit{dp} 值。

复杂度分析：

  1. 时间复杂度:O(n \times \textit{target})，其中 n 是数组的长度，\textit{target} 是整个数组的元素和的一半。需要计算出所有的状态，每个状态在进行转移时的时间复杂度为 O(1)。

  2. 空间复杂度：O(\textit{target})，其中 \textit{target} 是整个数组的元素和的一半。空间复杂度取决于 \textit{dp} 数组，在不进行空间优化的情况下，空间复杂度是 O(n \times \textit{target})，在进行空间优化的情况下，空间复杂度可以降到 O(\textit{target})。

编码实现

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int j = target; j >= num; --j) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }
}

精彩评论

跳转地址1：动态规划（转换为 0-1 背包问题）

前言

  • 关于背包问题的介绍，大家可以在互联网上搜索「背包九讲」进行学习，其中「0-1」背包问题是这些问题的基础。「力扣」上涉及的背包问题有「0-1」背包问题、完全背包问题、多重背包问题。
  • 本题解有些地方使用了「0-1」背包问题的描述，因此会不加解释的使用「背包」、「容量」这样的名词。
  • 说明：这里感谢很多朋友在这篇题解下提出的建议，对我的启发很大。本题解的阅读建议是：先浏览代码，然后再看代码之前的分析，能更有效理解知识点和整个问题的思考路径。题解后也增加了「总结」，供大家参考。

转换为 「0 – 1」 背包问题

  • 这道问题是我学习「背包」问题的入门问题，做这道题需要做一个等价转换：是否可以从输入数组中挑选出一些正整数，使得这些数的和 等于 整个数组元素的和的一半。很坦白地说，如果不是老师告诉我可以这样想，我很难想出来。容易知道：数组的和一定得是偶数。
  • 本题与 0-1 背包问题有一个很大的不同，即：
    • 0-1 背包问题选取的物品的容积总量 不能超过 规定的总量；
    • 本题选取的数字之和需要 恰好等于 规定的和的一半。
  • 这一点区别，决定了在初始化的时候，所有的值应该初始化为 false。 （《背包九讲》的作者在介绍 「0-1 背包」问题的时候，有强调过这点区别。）

「0 – 1」 背包问题的思路

  • 作为「0-1 背包问题」，它的特点是：「每个数只能用一次」。解决的基本思路是：物品一个一个选，容量也一点一点增加去考虑，这一点是「动态规划」的思想，特别重要。
    在实际生活中，我们也是这样做的，一个一个地尝试把候选物品放入「背包」，通过比较得出一个物品要不要拿走。
  • 具体做法是：画一个 len 行，target + 1 列的表格。这里 len 是物品的个数，target 是背包的容量。len 行表示一个一个物品考虑，target + 1多出来的那 1 列，表示背包容量从 0 开始考虑。很多时候，我们需要考虑这个容量为 0 的数值。

状态与状态转移方程

  • 状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于 j。
  • 状态转移方程：很多时候，状态转移方程思考的角度是「分类讨论」，对于「0-1 背包问题」而言就是「当前考虑到的数字选与不选」。
    • 不选择 nums[i]，如果在 [0, i – 1] 这个子区间内已经有一部分元素，使得它们的和为 j ，那么 dp[i][j] = true；
    • 选择 nums[i]，如果在 [0, i – 1] 这个子区间内就得找到一部分元素，使得它们的和为 j – nums[i]。

  • 状态转移方程：dp[i][j] = dp[i – 1][j] or dp[i – 1][j – nums[i]]

  • 一般写出状态转移方程以后，就需要考虑初始化条件。

    • j – nums[i] 作为数组的下标，一定得保证大于等于 0 ，因此 nums[i] <= j；
    • 注意到一种非常特殊的情况：j 恰好等于 nums[i]，即单独 nums[j] 这个数恰好等于此时「背包的容积」 j，这也是符合题意的。
  • 因此完整的状态转移方程是：

$$
dp[i][j]=
\begin{cases}
dp[i – 1][j], &
\\ true, & nums[i] = j
\\ dp[i – 1][j – nums[i]], & nums[i] < j
\end{cases}
$$

  • 友情提示：这一点在刚开始学习的时候，可能会觉得很奇怪。理解的办法是：拿题目中的示例，画一个表格，自己模拟一遍程序是如何「填表」的行为，就很清楚为什么状态数组降到 1 行的时候，需要「从后前向」填表。
    • 「从后向前」 写的过程中，一旦 nums[i] <= j 不满足，可以马上退出当前循环，因为后面的 j 的值肯定越来越小，没有必要继续做判断，直接进入外层循环的下一层。相当于也是一个剪枝，这一点是「从前向后」填表所不具备的。
  • 说明：如果对空间优化技巧还有疑惑的朋友，本题解下的精选评论也解释了如何理解这个空间优化的技巧，请大家前往观看。
  • 参考代码 3：只展示了使用一维表格，并且「从后向前」填表格的代码。
编码实现
public class Solution {

    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        if (nums[0] <= target) {
            dp[nums[0]] = true;
        }
        for (int i = 1; i < len; i++) {
            for (int j = target; nums[i] <= j; j--) {
                if (dp[target]) {
                    return true;
                }
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

复杂度分析：

  1. 时间复杂度:O(NC)，这里 N 是数组元素的个数，C 是数组元素的和的一半。。

  2. 空间复杂度：O(C)。减少了物品那个维度，无论来多少个数，用一行表示状态就够了。

总结


– 「0-1 背包」问题是一类非常重要的动态规划问题，一开始学习的时候，可能会觉得比较陌生。建议动笔计算，手动模拟填表的过程，其实就是画表格。这个过程非常重要，自己动手填过表，更能加深体会程序是如何执行的，也能更好地理解「空间优化」技巧的思路和好处。

– 在编写代码完成以后，把数组 dp 打印出来，看看是不是与自己手算的一样。以加深体会动态规划的设计思想：「不是直接面对问题求解，而是从一个最小规模的问题开始，新问的最优解均是由比它规模还小的子问题的最优解转换得到，在求解的过程中记录每一步的结果，直至所要求的问题得到解」。

思考

  • 最后思考为什么题目说是正整数，有 0 是否可以，有实数可以吗，有负数可以吗？
    • 0 的存在意义不大，放在哪个子集都是可以的；
    • 实数有可能是无理数，也可能是无限不循环小数，在计算整个数组元素的和的一半，要除法，然后在比较两个子集元素的和是否相等的时候，就会遇到精度的问题；
    • 再说负数，负数其实也是可以存在的，但要用到「回溯搜算法」解决。

相关问题

US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

5 × 5 =