C++ में Partition to K Equal Sum Subsets

मान लीजिए हमारे पास nums नामक एक पूर्णांक सरणी और एक धनात्मक पूर्णांक k है, जांचें कि क्या इस सरणी को k गैर-खाली उपसमुच्चयों (subsets) में विभाजित करना संभव है जिनके योग सभी समान हैं। इसलिए यदि सरणी [4,3,2,3,5,2,1] जैसी है और k = 4, तो परिणाम True होगा, क्योंकि दी गई सरणी को चार उपसरणियों जैसे [[5], [1,4], [2,3], [2,3]] में विभाजित किया जा सकता है जिनके योग समान हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• dp और total नामक दो तालिकाएँ परिभाषित करें जिनका आकार 2^n हो,
• दी गई सरणी nums को क्रमबद्ध करें, sum := nums सरणी में सभी तत्वों का योग सेट करें
• यदि sum mod k शून्येतर है OR nums का अंतिम तत्व > sum / k है, तो false लौटाएं
• dp[0] := true सेट करें और sum := sum / k
• i को 0 से 2^n तक की रेंज में
  • यदि dp[i] शून्येतर है, तो
    • j को 0 से तक की रेंज में
      • temp := i OR 2 ^ j
      • यदि temp i के समान नहीं है, तो
        • यदि nums[j] <= sum - total[i] mod sum, तो dp[temp] := true
        • total[temp] := total[i] + nums[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