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