31 lines
931 B
C++
31 lines
931 B
C++
#include "s0416_partition_equal_subset_sum.hpp"
|
|
|
|
bool S0416::canPartition(vector<int>& nums) {
|
|
int len = nums.size();
|
|
if (len < 2) return false;
|
|
int sum{0};
|
|
int maxVal = nums[0];
|
|
for (int i{0}; i < len; ++i) {
|
|
sum += nums[i];
|
|
if (nums[i] > maxVal) maxVal = nums[i];
|
|
}
|
|
// 如果为奇数则返回 false
|
|
if (sum % 2 != 0) return false;
|
|
// sum 除以 2 得到我们的目标值
|
|
int target = sum >> 1;
|
|
// 如果最大值大于目标值那就没必要再找了,因为除了目标值之外的所有值加起来也得不到 target
|
|
if (maxVal > target) return false;
|
|
// 如果最大值等于目标值也可以直接返回
|
|
if (maxVal == target) return true;
|
|
// 初始化
|
|
vector<int> dp(target + 1, false);
|
|
dp[nums[0]] = true;
|
|
// 开始遍历
|
|
for (int i{1}; i < len; ++i) {
|
|
for (int j = target; j >= nums[i]; --j) {
|
|
dp[j] = dp[j] || dp[j - nums[i]];
|
|
}
|
|
}
|
|
return dp[target];
|
|
}
|