C++-এ K সমান যোগফল উপসেটে বিভাজন

ধরুন আমাদের কাছে একটি পূর্ণসংখ্যার অ্যারে আছে যাকে nums বলা হয় এবং একটি ধনাত্মক পূর্ণসংখ্যা k, এই অ্যারেটিকে k অ-খালি উপসেটে ভাগ করা সম্ভব কিনা পরীক্ষা করুন যার যোগফল সব একই। সুতরাং যদি অ্যারেটি [4,3,2,3,5,2,1] এবং k =4 এর মতো হয় তবে ফলাফলটি True হবে, যেহেতু প্রদত্ত অ্যারেটিকে [[5], [[5] এর মতো চারটি সাবয়ারেতে ভাগ করা যায়। 1,4], [2,3], [2,3]] সমান রাশি সহ।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• dp নামে দুটি টেবিল সংজ্ঞায়িত করুন এবং মোট আকার 2^n,
• প্রদত্ত অ্যারের সংখ্যাগুলি সাজান, যোগফল সেট করুন :=সংখ্যা অ্যারের সমস্ত উপাদানের যোগফল
• যদি যোগফল mod k 0 না হয় বা সংখ্যার শেষ উপাদান> sum / k, তাহলে মিথ্যা ফেরত দিন
• dp[0] সেট করুন :=true এবং sum :=sum / k
• আমি 0 থেকে 2^n
  পরিসরে
  • যদি dp[i] অ শূন্য হয়, তাহলে
    0 থেকে ,
    পরিসরে j-এর জন্য
    • temp :=i OR 2 ^ j
    • যদি temp i এর মত না হয়, তাহলে
      • যদি সংখ্যা [j] <=যোগফল – মোট[i] মোড যোগ, তারপর dp[temp] :=সত্য
      • মোট[temp] :=মোট[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