C++ | Leetcode C++题解之第416题分割等和子集
题目：
题解：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return false;
}
int sum = 0, maxNum = 0;
for (auto& num : nums) {
sum += num;
maxNum = max(maxNum, num);
}
if (sum & 1) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
vector<int> dp(target + 1, 0);
dp[0] = true;
for (int i = 0; i < n; i++) {
int num = nums[i];
for (int j = target; j >= num; --j) {
dp[j] |= dp[j - num];
}
}
return dp[target];
}
};