05 August 2008
| DP递推公式 ： dp[tempSum] = dp[tempSum] | dp[tempSum - num]，之所以dp[tempSum]也是条件之一，是因为可能别的计算路径中已经让其为true了。 |
dp[tempSum] represents whether the tempSum can be achieved using the numbers in the array.
num is the current number being processed from the array.
dp[itempSum - num] represents whether the tempSum - num can be achieved using the numbers in the array.
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
class Solution {
public boolean canPartition(int[] nums) {
// Calculate the total sum of the array
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
// If the total sum is odd, it's impossible to divide it into two equal parts
if (totalSum % 2 != 0) {
return false;
}
// Calculate the target sum for each subset
int targetSum = totalSum / 2;
// Create a dp table to store the results
boolean[] dp = new boolean[targetSum + 1];
// 0个元素可以组成0
dp[0] = true;
// Iterate over the array and update the table
for (int num : nums) {
for (int tempSum = targetSum; tempSum >= num; tempSum--) { // 遍历所有的num，
// If the current sum is achievable, mark it as true
dp[tempSum] = dp[tempSum] || dp[tempSum - num];
}
}
return dp[targetSum];
}
}