在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数组中所有元素的总和
如果summodk非0或nums的最后一个元素>sum/k，则返回false
设置dp[0]：=true和sum：=sum/k
对于0到2^n的i
对于j，范围为0至，
如果nums[j]<=sum–total[i]modsum，则dp[temp]：=true
总数[temp]：=总数[i]+数字[j]
温度：=iOR2^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