给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
Related Topics
给定几个数字，看这几个数字能否凑出另一个数字，这个数字是这些数字的总和的一半，非常经典的0/1背包问题。
我们建立如下图中的DP数组
垂直方向上的表示使用从这个数字到他上面的数字，比如7这行，表示使用1,5,7这几个数字。而对应的横行表示要凑出的数字，对应坐标表示能否凑出这个数字。
比如纵列7横列8的格子，表示用1,5,7这几个数字能凑出值为8的和，这个答案是显然的，用1和7即可凑出来。
这里的横纵坐标上的0非常重要，表示不使用任何数字和凑出数字0的情况，显然这一行全是1，但是我们不着急先全都填上，先从左上角第一个格子开始。
- 第一行不使用任何数字，要凑出0的话，是可行的，先标记1，但是想凑出其他任何数字的话都是不可行的，都标记0，图中我们把标记0的格子全都省略不做标记了。
- 第二行，我们有了一个数字1，显然要凑出0的话，我们在上一行已经知道了，不使用任何数字就可以凑出0，直接把[0,0]里的值复制到[1,0]过来，而要凑齐1的话可以在之前0个数字凑齐0的基础上用上当前的数字1来凑到1，所以同样的我们把[0,0]的值复制到[1,1中来]
- 到了第三行，在原来拥有的数字集合0,1的基础上，我们又多出了数字5，那么同样的想要凑出数字0或者1的话，可以继续沿用原来的方案，那么就直接把之前的[1,0]和[1,1]的值复制到对应的[2,0]和[2,1]。而在原来的这两个凑数字的方案的基础上，额外加上现在多得到的5话，可以得到和位5或者6，那么同样对应的我们把[1,0]和[1,1]的值复制到[2,0+5]和[2,1+5]即[2,5]和[2,6]上。
- 此时是不是应该已经发现规律了。那么我们再看下第四行。在原有的数字0,1,5的基础上我们又多了个数字7，照样的，把原来第三行表示能凑出和的值复制下来，同时，对应往后移动7位的也设置成可以凑出来。即[3,0],[3,1],[3,5],[3,6],[3,7],[3,8]都设置为1表示可以凑出来。
- 后面的就不用多讲了，在这个过程中只要判断下看最终需要求的那个数字能否被凑出来，就可以立刻中断并返回结果了
除了上面主要的逻辑之外，如果一个数组的总和是一个奇数的话，那么必然是不能符合题意的，以及如果最大数字如果大于总和的一半的话也必然不能凑出来。
代码如下
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
int maxNum = 0;
for (int num : nums) {
sum += num;
maxNum = num > maxNum? num : maxNum;
}
if (sum % 2 == 1){
//总和为奇数，必然不能等分
return false;
}
if (maxNum > sum/2){
//最大的数值已经大于了总和的一半，也必然不能等分
return false;
}
int target = sum/2;
int[][] dp = new int[nums.length+1][target+1];
dp[0][0] = 1;
//下面部分dp的逻辑见图
for (int row = 1; row < nums.length; row++) {
for (int col = 0; col < (target + 1); col++) {
if (dp[row-1][col] == 1){
dp[row][col] = 1;
if ((col+nums[row])<=target){
dp[row][col+nums[row]] = 1;
}
}
if (dp[row][target] == 1){
return true;
}
}
}
return false;
}
}
发表评论