大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
原题链接
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
题解
先看和如果式奇数，返回false,否则除以2，然后看是否能够用拼凑出整合处于0
class Solution {
public:
const int INF = 0x3f3f3f3f;
bool canPartition(vector<int>& nums) {
if(nums.size() < 2)return false;
int sum = 0;
for(int i = 0;i < nums.size();i ++)sum += nums[i];
if(sum & 1)return false;
int target = sum / 2;
vector<int>f(target + 1,-INF);
f[0] = 0;
for(int i = 0;i < nums.size();i ++){
for(int j = target;j >= nums[i] ;j --){
f[j] = max(f[j],f[j - nums[i]] + nums[i]);
}
}
if(f[target] == target)return true;
return false;
}
};
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/168696.html原文链接：https://javaforall.net
