Phân vùng cho K Tập hợp con Tổng bằng nhau trong C ++

Giả sử chúng ta có một mảng các số nguyên gọi là num và một số nguyên dương k, hãy kiểm tra xem liệu có thể chia mảng này thành k tập con khác rỗng mà các tổng của chúng đều bằng nhau hay không. Vì vậy, nếu mảng giống như [4,3,2,3,5,2,1] và k =4, thì kết quả sẽ là True, vì mảng đã cho có thể được chia thành bốn mảng con như [[5], [ 1,4], [2,3], [2,3]] với các tổng bằng nhau.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• xác định hai bảng được gọi là dp và tổng kích thước 2 ^ n,
• sắp xếp các số mảng đã cho, đặt sum:=tổng của tất cả các phần tử trong mảng nums
• nếu sum mod k khác 0 HOẶC phần tử cuối cùng của nums> sum / k, thì trả về false
• đặt dp [0]:=true và sum:=sum / k
• cho tôi trong phạm vi 0 đến 2 ^ n
  • nếu dp [i] khác 0, thì
    • cho j trong phạm vi 0 đến,
      • tạm thời:=i HOẶC 2 ^ j
      • nếu nhiệt độ không giống với tôi, thì
        • nếu nums [j] <=sum - total [i] mod sum, thì dp [temp]:=true
        • total [temp]:=total [i] + nums [j]
      • khác xuất hiện từ vòng lặp
• return dp [(2 ^ n) - 1]

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

1