分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
1
2
3
| 输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
|
示例 2：
1
2
3
| 输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
|
提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
问题就相当于从数组中挑选数字组成的和恰好等于数组总和的一半，是01背包问题。
f[i][j]表示前i个数是否可以恰好组成j。
初始化f[i][0]=true,表示如果都不选，可以组成0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public boolean canPartition(int[] nums) {
int total = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
total += nums[i];
}
if (total % 2 == 1)
return false;
total /= 2;
boolean[][] f = new boolean[n + 1][total + 1];
for (int i = 0; i <= n; i++) {
f[i][0] = true;
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= total; j++) {
if (nums[i - 1] > j) {
f[i][j] = f[i - 1][j];
} else {
f[i][j] = f[i - 1][j] || f[i - 1][j - nums[i - 1]];
}
}
}
return f[n][total];
}
}
|
01背包可以优化为一维数组。注意第二层循环要倒序。
在二维数组中f[i][j]依赖于f[i-1][j]和f[i-1][j-nums[i-1]]，对应到矩阵中也就是当前格子只依赖于上一行的格子和左上角的一个格子，也就是依赖于上一行的旧数据。在一维数组中，如果正序更新，f[j] = f[j] || f[j - nums[i - 1]];,因为f[j-nums[i-1]]先于f[j]更新完了，所以f[j]依赖的是新数据，对应二维数组中的f[i][j-nums[i-1]]。所以要逆序更新。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public boolean canPartition(int[] nums) {
int total = 0;
int n = nums.length;
for (int i = 0; i < n; i++) {
total += nums[i];
}
if (total % 2 == 1)
return false;
total /= 2;
boolean[] f = new boolean[total + 1];
f[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = total; j >= 0; j--) {
if (nums[i - 1] <= j) {
f[j] = f[j] || f[j - nums[i - 1]];
}
}
}
return f[total];
}
}
|
