【LeetCode】【算法】416. 分割等和子集

LeetCode 416. 分割等和子集

题目描述

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

思路

和LeetCode 494.目标和很相似，这道题也是用动态数组可以求解的。

1. 对nums的所有元素求个sum，若sum % 2 != 0，则return false; 因为此时没办法分成两个等和子集
2. 定义dp数组dp[nums.length][bagSize +1]，其中bagSize = sum / 2;
3. 初始化dp数组：dp[0][nums[0]]=1;
4. 填充dp数组：嵌套循环，有两种可能性：
   I. nums[i] > j时，dp[i][j]=dp[i-1][j]
   II. 否则，求最值dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i])
5. 返回：dp[nums.length-1][bagSize]==bagSize
6. 为什么这里的递推式是求“最值”，我的理解是任何一个值都有可能是构成目标和的一部分

当然这可以用一维dp来解，因为nums[i]里面的数既是重量也是价值？但是我赶时间就没细看

代码

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false; // 和无法评分，则无法分成两个相等的子集

        int bagSize = sum / 2; // 目标和的结果

        // 动态数组定义与初始化
        int[][] dp = new int[nums.length][bagSize + 1];
        if (nums[0] <= bagSize) dp[0][nums[0]] = 1;

        // 填充动态数组
        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j < bagSize + 1; j++) {
                if (nums[i] > j) dp[i][j] = dp[i - 1][j];
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i]);
                }
            }
        }

        return dp[nums.length - 1][bagSize] == bagSize;
    }
}