[Leetcode] 416. Partition Equal Subset Sum | 分割等和子集

yPhantom 2020年02月02日 35次浏览

Given a non-empty array 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.

Note:

  1. Each of the array element will not exceed 100.
  2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

这道题让判断是否能将一个数组分成两个和相等的数组。

一开始看到是求和相关的数组题,我以为又是用的累加和法,然后仔细分析了下发现并不能解决。。。

其实转换下思路,这道题的实质是判断数组中是否能找到和为指定target的子数组。在这里target=sum/2。其实这是一道0/1背包问题。

背包问题可以直接搜索引擎搜索背包九讲。被转载了不知道多少遍了。。。

我们以dp[i][j]代表前i个数是否能得到和为j的子数组,因此对于每个数,我们都有选和不选两种情况。因此就有如下代码:

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {
            return false;
        }
        sum = sum >> 1;
        boolean[][] dp = new boolean[nums.length + 1][sum + 1];
        dp[0][0] = true;
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= sum; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[nums.length][sum];
    }
}

这里需要注意下初始化的几种情况:

  • dp[0][0] = true 代表一个数都没有和为0的情况,当然为true
  • dp[i][0] = true 代表有数,但是一个都不选,和为0的情况,也是true
  • dp[0][i] = false,这个不用说了

Accepted了就满足了吗?当然不是。上述代码存在优化的空间。也就是基础的0/1背包问题中,可以将二维dp数组优化成一维。此时代码如下:

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {
            return false;
        }
        sum = sum >> 1;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = sum; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[sum];
    }
}

这里有个问题就是,一维dp数组遍历时内层循环是逆序的。为什么呢?这是因为如果是顺序遍历的话,比如dp[1]或者dp[2]这种比较小的下标顺序遍历会直接更新它们的值,而在后面i - num时很有可能再次用到它们,这代表了这一个数被用了两次及以上,而在这一类只能用一次的背包问题中必须得逆序。如果一个数字不限制次数的话,可以是顺序的。

除了上述的背包解法,还可以用bfs的方法,思路也差不多,也是用或不用这个数字。

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {
            return false;
        }
        sum = sum >> 1;
        for (int num : nums) {  // corner case
            if (num > sum) {
                return false;
            }
        }
        return bfs(nums, nums.length - 1, 0, sum);
    }
    
    private boolean bfs(int[] nums, int j,  int cur, int sum) {
        if (j < 0 || j >= nums.length) {
            return false;
        }
        if (cur == sum) {
            return true;
        }
        return bfs(nums, j - 1, cur, sum) || bfs(nums, j - 1, cur + nums[j], sum);
    }
}

但是这个会超时。

参考链接

0/1 knapsack detailed explanation

0/1背包内层循环逆序原因

相关题目

494. Target Sum