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

解题思路

本质是从数组中选取一些数，使得其和为target，其中target=sum/2。

很明显，这是一道0-1背包的题目，用动态规划来解题，下面我们来找一下动态规划的递推公式和起始值。

定义dp数组：
boolean[][] dp[i][j]：由前i个数字，能否组成合为j的值

递推公式：

• 如果j >= nums[i]: dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]
  • dp[i-1][j] 对应不选当前nums[i]到背包
  • dp[i-1][j-nums[i]] 对应选当前nums[i]到背包
• 如果j < nums[i]: dp[i][j] = dp[i-1][j]
  • 超过背包的容量，肯定不能选

起始值：
dp[i][0] = true：由i个数字，组成和为0，永远为true，因为只需要所有数字都不选即可

Java代码

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        // 前i个数组成合为j
        boolean[][] dp = new boolean[n+1][target+1];
        for(int i = 0; i <= n; i++){
            dp[i][0] = true;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= target; j++){
                if(j < nums[i-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][target];
    }
}

因为整个递推公式，dp[i][j] 只与它前面的值有关，所以我们可以优化空间为一维，并且改成从后往前遍历。

优化空间复杂度后：

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

总结

这道题通过变形之后，可以变成一个典型的0-1背包的题目，用动态规划来解决。

值得注意的是，我们给出了优化空间复杂度之后的解法，注意需要将j从后往前遍历，否则会被覆盖，导致错误的结果。