C ++中的分区相等子集总和

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个仅包含正数的非空数组，我们必须确定该数组是否可以划分为两个子集，以使两个子集中的元素之和相同。因此，如果输入类似于[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

以上是 C ++中的分区相等子集总和 的全部内容， 来源链接： utcz.com/z/327312.html

回到顶部