数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中将数组划分成 K 个和相等子集
假设我们有一个名为 nums 的整数数组和一个正整数 k，检查是否可以将此数组分成 k 个非空子集，这些子集的和都相同。所以如果数组类似于 [4,3,2,3,5,2,1] 且 k = 4，则结果将为 True，因为给定数组可以分成四个子数组，例如 [[5], [1,4], [2,3], [2,3]]，它们的和相等。
为了解决这个问题，我们将遵循以下步骤：
- 定义两个名为 dp 和 total 的大小为 2^n 的表，
- 对给定的数组 nums 进行排序，设置 sum := nums 数组中所有元素的和
- 如果 sum mod k 不为 0 或 nums 的最后一个元素 > sum / k，则返回 false
- 设置 dp[0] := true 并设置 sum := sum / k
- 对于 i 的范围从 0 到 2^n
- 如果 dp[i] 不为零，则
- 对于 j 的范围从 0 到，
- temp := i OR 2 ^ j
- 如果 temp 与 i 不相同，则
- 如果 nums[j] <= sum – total[i] mod sum，则 dp[temp] := true
- total[temp] := total[i] + nums[j]
- 否则退出循环
- 对于 j 的范围从 0 到，
- 如果 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
更新于：2020 年 4 月 29 日
355 次浏览
广告