1，问题描述
416. 分割等和子集
难度：中等
给你一个 只包含正整数 的 非空 数组 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
2，初步思考
模式识别：01背包问题
问题的本质是有一个容量为sum/2的背包，求里面可以最大装的数字和是否为sum/2
3，代码处理
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| import java.util.Arrays;
public class _416分割等和子集 {
public boolean canPartition_2d(int[] nums) {
int sum = Arrays.stream(nums).sum();
int n = nums.length;
if (sum % 2 == 1) return false;
int half = sum >> 1;
int[][] dp = new int[n + 1][half + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= half; j++) {
int cur = nums[i - 1];
if (cur > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - cur] + cur);
}
}
}
return dp[n][half] == half;
}
public boolean canPartition_1d(int[] nums) {
int sum = Arrays.stream(nums).sum();
int n = nums.length;
if (sum % 2 == 1) return false;
int half = sum >> 1;
int[] dp = new int[half + 1];
for (int i = 1; i <= n; i++) {
for (int j = half; j >= nums[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i - 1]] + nums[i - 1]);
}
}
return dp[half] == half;
}
public static void main(String[] args) {
_416分割等和子集 partition = new _416分割等和子集();
System.out.println(partition.canPartition_1d(new int[]{1, 5, 11, 5}));
}
}
|
4，拓展知识点
背包问题类型：
01背包：每件物品只有一个
完全背包：每种物品有无限个
多重背包：每种物品有限定的个数，二进制优化