C++ में K समान सम सबसेट का विभाजन

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है जिसे अंक और एक धनात्मक पूर्णांक k कहा जाता है, जाँच करें कि क्या इस सरणी को k गैर-रिक्त उपसमुच्चय में विभाजित करना संभव है, जिनके योग समान हैं। तो अगर सरणी [4,3,2,3,5,2,1] और k =4 की तरह है, तो परिणाम सही होगा, क्योंकि दिए गए सरणी को चार उप-सरणी में विभाजित किया जा सकता है जैसे [[5], [ 1,4], [2,3], [2,3]] बराबर राशि के साथ।

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

• dp नामक दो तालिका परिभाषित करें और कुल आकार 2^n,
• दिए गए सरणी संख्याओं को क्रमबद्ध करें, योग सेट करें:=अंक सरणी में सभी तत्वों का योग
• यदि योग mod k गैर 0 है या अंकों का अंतिम तत्व है> योग / k, तो झूठी वापसी करें
• सेट dp[0] :=true and sum :=sum / k
• मैं के लिए 0 से 2^n की सीमा में
  • यदि dp[i] शून्य नहीं है, तो
    • जे के लिए 0 से ,
      . की सीमा में
      • अस्थायी:=मैं या 2 ^ जे
      • अगर टेम्परेचर i के समान नहीं है, तो
        • यदि अंक [जे] <=योग - कुल [i] मॉड योग, तो डीपी [अस्थायी]:=सत्य
        • कुल [अस्थायी] :=कुल[i] + अंक [j]
      • अन्यथा लूप से बाहर आएं
• रिटर्न डीपी[(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