আমরা C++ এ সমান সমষ্টির k-পার্টিশনের সাথে একটি তালিকা ভাগ করতে পারি কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে nums নামে একটি সংখ্যার তালিকা রয়েছে এবং আরেকটি মান k, আমাদের পরীক্ষা করতে হবে যে সংখ্যাগুলিকে k বিভিন্ন উপসেটে ভাগ করা সম্ভব যেখানে প্রতিটি উপসেটের যোগফল একই।

সুতরাং, ইনপুট যদি nums =[4, 2, 6, 5, 1, 6, 3] k =3 এর মত হয়, তাহলে আউটপুট হবে True, যেমন আমরা সেগুলিকে এভাবে পার্টিশন করতে পারি:[6, 3], [6] , 2, 1], এবং [4, 5]।

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

• একটি ফাংশন চেক সংজ্ঞায়িত করুন(), এটি একটি অ্যারে v নেবে,
• আরম্ভ করার জন্য i :=1, যখন i
• যদি v[i] v[0] এর সমান না হয়, তাহলে −
  • মিথ্যে ফেরত দিন

উদাহরণ (C++)

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool check(vector<int>& v) {
      for (int i = 1; i < v.size(); i++) {
         if (v[i] != v[0])
            return false;
      }
      return true;
   }
   bool dfs(int idx, vector<int>& nums, vector<int>& temp) {
      if (idx == nums.size()) {
         return check(temp);
      }
      bool ret = false;
      for (int i = 0; i < temp.size(); i++) {
         temp[i] += nums[idx];
         ret = dfs(idx + 1, nums, temp);
         if (ret)
            return true;
         temp[i] -= nums[idx];
      }
      return false;
   }
   bool solve(vector<int>& nums, int k) {
      vector<int> temp(k);
      return dfs(0, nums, temp);
   }
};
bool solve(vector<int>& nums, int k) {
   return (new Solution())->solve(nums, k);
}
int main(){
   vector<int> v = {4, 2, 6, 5, 1, 6, 3};
   int k = 3;
   cout << solve(v, 3);
}

ইনপুট

{4, 2, 6, 5, 1, 6, 3}, 3

আউটপুট

1