यह जाँचने के लिए प्रोग्राम कि क्या हम C++ में समान योग के k-विभाजन वाली सूची को विभाजित कर सकते हैं

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k, हमें यह जांचना होगा कि क्या संख्याओं को k के विभिन्न उपसमुच्चय में विभाजित करना संभव है जहां प्रत्येक उपसमुच्चय का योग समान है।

इसलिए, यदि इनपुट संख्या =[4, 2, 6, 5, 1, 6, 3] k =3 की तरह है, तो आउटपुट सही होगा, क्योंकि हम उन्हें विभाजित कर सकते हैं जैसे:[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