01背包
思路
代码(滚动数组优化后)
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum=0;
for(auto& num:nums) sum+=num;
if(sum%2) return false;
int target=sum/2;
int n=nums.size();
bool f[target+1];
memset(f,0,sizeof f);
f[0]=true;
for(int i=1;i<=n;i++)
for(int j=target;j>=nums[i-1];j--)
f[j]|=f[j-nums[i-1]];
return f[target];
}
};