資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告