C++ में माचिस की तीलियों से वर्ग तक

मान लीजिए कि एक छोटी सी मैच गर्ल है। और हमें ठीक-ठीक पता है कि छोटी माचिस की तीली के पास कौन सी माचिस की तीली है, हमें उन सभी माचिस की तीलियों का उपयोग करके एक वर्ग बनाने का तरीका खोजना होगा। हमें कोई छड़ी नहीं तोड़नी चाहिए, लेकिन हम उन्हें जोड़ सकते हैं, और प्रत्येक माचिस को ठीक एक बार इस्तेमाल किया जाना चाहिए। हमारे इनपुट में लड़की की कई माचिस की तीलियाँ होंगी, जिन्हें उनकी छड़ी की लंबाई के साथ दर्शाया जाएगा। हमारा आउटपुट या तो सही होगा या गलत, यह दर्शाने के लिए कि क्या हम मैच की लड़की के पास सभी माचिस की तीलियों का उपयोग करके एक वर्ग बना सकते हैं। तो अगर इनपुट [1,1,2,2,2] जैसा है, तो उत्तर सही होगा, क्योंकि हम लंबाई 2 का एक वर्ग बना सकते हैं, एक तरफ लंबाई 1 की दो छड़ें होंगी।

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

• एक पुनरावर्ती विधि को परिभाषित करें जिसे हल () कहा जाता है। यह सूचकांक, रकम सरणी, लक्ष्य और अंक सरणी लेगा। तो यह इस प्रकार काम करेगा -
• यदि अनुक्रमणिका>=अंकों का आकार, तो
  • समारोह [0], योग [1] और योग [2] सभी टार्गर के समान होने पर सही हो जाते हैं
• मैं के लिए 0 से 3 की सीमा में −
  • अगर sums[i] + nums[index]> टारगेट करें, तो लूप के अगले हिस्से को छोड़ दें
  • योग [i] :=योग [i] + अंक [सूचकांक]
  • यदि हल (इंडेक्स + 1, योग, लक्ष्य, अंक) सत्य है, तो सत्य लौटाएं
  • योग [i] :=योग [i] – अंक [सूचकांक]
• झूठी वापसी
• मुख्य विधि से, निम्न कार्य करें -
• यदि अंकों में कोई तत्व नहीं है, तो झूठी वापसी करें
• x :=0
• मेरे लिए 0 से लेकर अंकों के आकार तक, x को अंकों से बढ़ाएँ[j]
• यदि x, 4 से विभाज्य है, तो असत्य लौटाएं
• अंक सरणी क्रमबद्ध करें
• आकार 4 का एक सरणी योग बनाएं
• रिटर्न सॉल्व (0, योग, x/4, अंक)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool solve(int idx, vector <int>& sums, int target, vector <int>& nums){
      if(idx >= nums.size()){
         return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == target;
      }
      for(int i = 0; i < 4; i++){
         if(sums[i] + nums[idx] > target)continue;
         sums[i] += nums[idx];
         if(solve(idx + 1, sums, target, nums)) return true;
         sums[i] -= nums[idx];
      }
      return false;
   }
   bool makesquare(vector<int>& nums) {
      if(nums.size() == 0) return false;
      int x = 0;
      for(int i = 0; i < nums.size(); i++){
         x += nums[i];
      }
      if(x % 4) return false;
      sort(nums.rbegin(), nums.rend());
      vector <int> sum(4);
      return solve(0, sum,x / 4, nums);
   }
};
main(){
   vector<int> v = {1,1,2,2,2};
   Solution ob;
   cout << (ob.makesquare(v));
}

इनपुट

[1,1,2,2,2]

आउटपुट

1