C ++中的分区相等子集总和
假设我们有一个仅包含正数的非空数组，我们必须确定该数组是否可以划分为两个子集，以使两个子集中的元素之和相同。因此，如果输入类似于[1,5,11,5]，则输出为true。由于此数组可以划分为[1、5、5]和[11]
为了解决这个问题，我们将遵循以下步骤-
n：=数组的大小
和：=0
对于我：=0至n–1
sum：=sum+nums[i]
如果总和是奇数，则返回false
总和：=总和/2
创建一个称为dp的数组，大小为sum+1
dp[0]：=true
对于i，范围为0至n–1
dp[j]：=dp[j]或dp[j-x]，不为0
x：=nums[i]
对于j：=求和到j–x
返回dp[sum]
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i =0;i<n;i++)sum+=nums[i];
if(sum&1)return false;
sum/=2;
vector <bool> dp(sum+1);
dp[0] = true;
for(int i =0;i<n;i++){
int x = nums[i];
for(int j =sum;j-x>=0;j--){
dp[j]=dp[j] || dp[j-x];
}
}
return dp[sum];
}
};
main(){
Solution ob;
vector<int> v = {1,5,11,5};
cout << ob.canPartition(v);
}输入值
[1,5,11,5]
输出结果
1
热门推荐
8 带清的简短祝福语
10 给婴儿祝福语简短的话
11 元旦联谊祝福语简短精辟
12 圣诞饭店祝福语大全简短
13 对航母的祝福语简短
14 班级集体生日祝福语简短
15 写给老师祝福语简短大学
16 儿女的生日祝福语简短
17 关于好的祝福语简短
18 婆婆生日祝福语简短的