关于leetcode:leetcode-416-Partition-Equal-Subset-Sum-分割等和子集中等

1次阅读

共计 922 个字符，预计需要花费 3 分钟才能阅读完成。

标签: 动静布局

https://leetcode.cn/problems/partition-equal-subset-sum

给你一个只蕴含正整数的非空数组 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

设所有数字和为 sum，咱们的指标是选取一个子数组，使它的总和为 sum/2，定义二维 boolean 数组 dpi，其意义是应用前 i 个数字的和能不能形成整数 j。咱们须要把每个地位都进行遍历，同时也要对 0 -target 之间的所有负数进行遍历。状态转移方程是，遍历到 i 地位时能不能形成 target= 后面的数字的和能形成 target|| 后面的数字能形成 target-nums[i]。这两个状态别离是选不选取 nums[i] 的两种状况，如果有一种状况成立即可：
dpi = dpi-1 || dpi-1]

public class Solution {public boolean canPartition(int[] nums) {
        // 数组求和
        int sum = Arrays.stream(nums).sum();
        // 场景 1：和为奇数不能均分
        if (sum % 2 == 1) {return false;}
        int target = sum / 2;
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {for (int j = 0; 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];
    }
}