LeetCode 416. Partition Equal Subset Sum

Problem

LeetCode 416. Partition Equal Subset Sum

1. 题目简述

给出一个非空的正整数数组，判断该数组是否能一分为二，且两个子集的数值和相等。例如：

Input: [1, 5, 11, 5]

Output: true

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

2. 算法思路

相关问题：

1. LeetCode 698. Partition to K Equal Sum Subsets（待做）

经典的子集背包问题（后面抽空会写一篇背包问题总结），完全背包问题是LeetCode 518. Coin Change 2。

DP

我们首先要判断数组和是否是偶数，如果是，则OK，我们可以继续往下找；如果是基数，则pass。

然后我们算出的target = sum / 2。也就是说我们需要从数组中找出一个子集，使得其和为target。

我们写dp方程的时候先来判断一下我们有多少个变量，一个是数字个数，另一个是target大小，因此我们推测这是一个二维dp。dp[i][j]为前i个数，和为j的可能性，true或者false。

那么我们可以得出如下递推式：

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

而且，我们可以知道的是每一次计算dp值的时候，只依赖于上一次的结果，因此我们可以将空间复杂度降到一维。

时间复杂度：O（n ^ 2）。因为target为 n / 2，需要遍历从0到target。

空间复杂度：O(n）。n为nums长度。

Attention:如果是使用一维数组进行dp的话，target的遍历要从后向前，因为它会依赖上一次计算前面的dp值，如果从前向后遍历，则会覆盖掉。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 如果和为奇数，pass
        if (sum % 2 == 1) {
            return false;
        }

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

        for (int i = 1; i <= nums.length; i++) {
            for (int j = target; j > 0; j--) {
                if (j - nums[i - 1] >= 0) {
                    // 这里的dp[j]就是上一次的i-1的dp[j]
                    dp[j] = dp[j] || dp[j - nums[i - 1]];
                } else {
                    dp[j] = dp[j];
                }
            }
        }

        return dp[target];
    }
}