在C ++中对K个相等和子集的分区

假设我们有一个称为nums的整数数组和一个正整数k，请检查是否有可能将此数组划分为总和相同的k个非空子集。因此，如果数组类似于[4,3,2,3,5,2,1]且k = 4，则结果将为True，因为给定的数组可以分为四个子数组，例如[[5]，[ 1,4]，[2,3]，[2,3]]的总和相等。

为了解决这个问题，我们将遵循以下步骤-

• 定义两个称为dp的表，其总大小为2 ^ n，

• 对给定的数组num进行排序，设置sum：= nums数组中所有元素的总和

• 如果sum mod k非0或nums的最后一个元素> sum / k，则返回false

• 设置dp [0]：= true和sum：= sum / k

• 对于0到2 ^ n的i

• 对于j，范围为0至，

• 如果nums [j] <= sum – total [i] mod sum，则dp [temp]：= true

• 总数[temp]：=总数[i] +数字[j]

• 温度：= i OR 2 ^ j

• 如果temp与我不同，则

• 否则从循环中出来

• 如果dp [i]不为零，则

• 返回dp [（2 ^ n）-1]

例子（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool canPartitionKSubsets(vector<int>& nums, int k) {
      int n = nums.size();
      vector <bool> dp(1 << n);
      vector <int> total(1 << n);
      sort(nums.begin(), nums.end());
      int sum = 0;
      for(int i = 0; i < nums.size(); i++)sum += nums[i];
      if(sum % k || nums[nums.size() - 1] > sum / k) return false;
      dp[0] = true;
      sum /= k;
      for(int i = 0; i < (1 << n); i++){
         if(dp[i]){
            for(int j = 0; j < n; j++){
               int temp = i | (1 << j);
               if(temp != i){
                  if(nums[j] <= sum - (total[i] % sum)){
                     dp[temp] = true;
                     total[temp] = total[i] + nums[j];
                  }
                  else{
                     break;
                  }
               }
            }
         }
      }
      return dp[(1 << n) - 1];
   }
};
main(){
   Solution ob;
   vector<int> v = {4,3,2,3,5,2,1};
   cout << (ob.canPartitionKSubsets(v, 4));
}

输入值

[4,3,2,3,5,2,1]
4

输出结果

1