416. Partition Equal Subset Sum
0/1 knapsack (01背包) 问题,找能否数组有一部分数字加起来是总价值的一半。 参考 322. Coin Change
class Solution {
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) {
return true;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
sum = sum / 2;
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
for (int i = 0; i < nums.length; i++) {
for (int j = sum; j >= nums[i]; j--) {
dp[j] == dp[j] || dp[j - nums[i]]; // 不选/选nums[i]
}
}
return dp[dp.length - 1];
}
}