การแบ่งพาร์ติชันไปยังเซตย่อยของ K Equal Sum ใน C++

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่เรียกว่า nums และจำนวนเต็มบวก k ให้ตรวจสอบว่าเป็นไปได้หรือไม่ที่จะแบ่งอาร์เรย์นี้เป็นชุดย่อยที่ไม่ว่างเปล่า k ซึ่งมีผลรวมเหมือนกันทั้งหมด ดังนั้นหากอาร์เรย์เป็นเหมือน [4,3,2,3,5,2,1] และ k =4 ผลลัพธ์จะเป็น True เนื่องจากอาร์เรย์ที่กำหนดสามารถแบ่งออกเป็นสี่อาร์เรย์ย่อยเช่น [[5], [ 1,4], [2,3], [2,3]] ด้วยผลรวมเท่ากัน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดสองตารางที่เรียกว่า dp และรวมเป็นขนาด 2^n
• จัดเรียงจำนวนอาร์เรย์ที่กำหนด ตั้งค่า sum :=ผลรวมขององค์ประกอบทั้งหมดในอาร์เรย์ nums
• ถ้า sum mod k ไม่ใช่ 0 หรือองค์ประกอบสุดท้ายของ nums> sum / k ให้คืนค่าเท็จ
• set dp[0] :=true และ sum :=sum / k
• สำหรับฉันอยู่ในช่วง 0 ถึง 2^n
  • ถ้า dp[i] ไม่ใช่ศูนย์ ดังนั้น
    • สำหรับ j ในช่วง 0 ถึง ,
      • อุณหภูมิ :=i หรือ 2 ^ j
      • ถ้า temp ไม่เหมือนกับ i แล้ว
        • ถ้า nums[j] <=sum – Total[i] mod sum แล้ว dp[temp] :=true
        • ผลรวม[อุณหภูมิ] :=ยอดรวม[i] + จำนวน[j]
      • อย่างอื่นออกมาจากวง
• ผลตอบแทน 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