分割等和子集-leetcode

题目描述

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

解法一

思路：

0-1 背包问题的变种。要将数组分割成两个元素和相等的子集，实际上就等价于：能否从数组中挑出一些元素，使得这些元素的总和刚好等于整个数组总和的一半。

dp[i][j] 表示：能否从前 i 个元素中挑选出若干个，使得它们的和恰好等于 j

对于当前的数字 nums[i]，我们只有两种选择：选 或者 不选。

• 情况 1：不选 nums[i] 如果我们不把 nums[i] 放入子集中，那么能否凑成和为 j，完全取决于前 i-1 个元素。 此时：dp[i][j] = dp[i-1][j]
• 情况 2：选 nums[i] 前提是当前的目标和 j 必须大于等于 nums[i]（背包得装得下）。如果选了它，那么剩下的目标和就是 j - nums[i]，我们需要看前 i-1 个元素能否凑出 j - nums[i]。 此时：dp[i][j] = dp[i-1][j - nums[i]]

状态转移方程：

如果 j >= nums[i] :dp[i][j] = dp[i-1][j] 或者 dp[i-1][j - nums[i]]  (只要有一个为 true，结果就为 true)
如果 j < nums[i] :dp[i][j] = dp[i-1][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[nums.length + 1][target + 1];dp[0][0] = true;for (int i = 1; i <= nums.length; i++) {for (int j = 0; j <= target; j++) {if (j - nums[i - 1] >= 0) {dp[i][j] = dp[i - 1][j - nums[i - 1]]||dp[i - 1][j];}else dp[i][j] = dp[i - 1][j];}}return dp[nums.length][target];}
}