LeetCode日记— 416. Partition Equal Subset Sum

碎碎念:周末在宿舍真的太吵了。。学个der的习。现在好好学雅思好好刷题吧。不然就离开内卷赛道,不然就找个好工。

题目如下:

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

这题的本质就是一个np完全问题(恕我愚笨,我没有咋看懂wiki的数学推演),这题某种意义上可以转换成0-1背包问题。(关于背包问题

思路:

对不起,我太笨了,没想出来怎么解,以下思路皆来自于了lc官方题解(加上一些我自己的加工。

首先我们对一些显然不可能的情况进行剪枝处理:

一、 如果nums长度小于2那肯定无法分为两段,故返回false。

二、如果nums的总和为奇数,那说明也无法分成两个相等子集,则返回false。

三、如果sum为偶数了,则得到一个target=sum/2.若nums中最大数max大于target,那无论如何都不可能分为两个相等子集了,故返回false。

创建dp数组及其解释,见官方解释。

我自己的解释在代码的注释部分。

最终代码如下:

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;
        }
//剪枝操作后进行dp的初始化,行数i表示在0-i之间选取数,j表示目标和,若集合内存在某几个数和等于j则布尔值为true,否则反之,最终返回的结果应该是dp[N-1][Target]
        boolean[][] dp = new boolean[n][target + 1];
//j等于0时必然是true
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }
//只能选nums【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) {
//若选取了第i个数进入背包,则是否为true取决于未放入切目标和为j-nums[i]时是否为true,若不放入背包则结果与dp [i - 1][j]相同。两者一个为true就可以了
                    dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
                } else {
//j比nums【i】小则没有选取的必要了                    
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n - 1][target];
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

观察上面的代码,我们发现其实每次的结果都与上一行有关,那么我们只需要一个一维的滚动数组,就可以完成这个目标,同时降低空间复杂度。

此时的转移方程为:

dp[j] = dp[j]|dp[j-nums[i]]

返回值是dp[target]

需要注意的一个细节是,这时我们要从大往小遍历数组,否则每次更新时的dp[j-nums[i]]就都是已经更新过的了。

代码如下:

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];
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
点赞

发表评论

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