LeetCode 416 分割等和子集
題目鏈接
給定一個只包含正整數的非空陣列，是否可以將這個陣列分割成兩個子集，使得兩個子集的元素和相等，
注意:
每個陣列中的元素不會超過 100
陣列的大小不會超過 200
示例 1:
輸入: [1, 5, 11, 5]
輸出: true
解釋: 陣列可以分割成 [1, 5, 5] 和 [11].
示例 2:
輸入: [1, 2, 3, 5]
輸出: false
解釋: 陣列不能分割成兩個元素和相等的子集.
典型的背包問題~
首先和為奇數時肯定不能平均分，對和為偶數的情況就進行
01
01
01 背包，看最大值能否等于
s
u
m
2
\frac{sum}{2}
2sum? 即可，AC代碼如下:
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum=0;
for(auto i:nums) sum+=i;
if(sum%2) return 0;
int dp[sum+1],ans=0;
memset(dp,0,sizeof(dp));
for(int i=0;i<nums.size();i++){
for(int j=sum/2;j>=nums[i];j--){
dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
ans=max(ans,dp[j]);
}
}
return (ans==sum/2);
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/168803.html
標籤：其他