Partition Equal Subset Sum

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

解:https://gitee.com/footmanff/leetcode/blob/master/src/main/java/com/footmanff/leetcode/P416.java

动态规划

基本思想:如果前 n 个数,组成的和是 s1、s2,此时如果再加上下一个数 next,组成的和是 0 + next、s1 + next、s2 + next。

比如数列:1 5 11 5。

已知前 0 个数,能组成和 0。

那么前 1 个数,组成 0、1

那么前 2 个数,组成 0、1、5、6

那么前 3 个数,组成 0、1、5、6、11、12、16、17,此时 11 刚好命中目标结果

用一个数组 a,a[i] 表示可以通过从数列中取若干个数,满足和为 i。

每次取一个 num,如果从前向后维护数组,后面的位会被重复维护,除非用其他的标志位过滤。另一种思路是从后往前维护。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
int half = sum / 2;

int[] dp = new int[sum + 1];
dp[0] = 1;
for (int num : nums) {
for (int i = sum; i >= num; i--) {
if (dp[i - num] == 1) {
dp[i] = 1;
if (i == half) {
return true;
}
}
}
}
return false;
}

资料:https://www.bilibili.com/video/BV1AW411y7So