मान लीजिए एक छोटी माचिस वाली लड़की है। और हम ठीक से जानते हैं कि छोटी माचिस वाली लड़की के पास कौन सी माचिस की तीलियां हैं, हमें एक रास्ता ढूंढना है जिससे हम उन सभी माचिस की तीलियों का उपयोग करके एक वर्ग बना सकें। हमें किसी भी छड़ी को नहीं तोड़ना चाहिए, लेकिन हम उन्हें जोड़ सकते हैं, और प्रत्येक माचिस की तीली का उपयोग ठीक एक बार किया जाना चाहिए। हमारा इनपुट लड़की के पास मौजूद कई माचिस की तीलियां होंगी, जो उनकी छड़ी की लंबाई से दर्शाई गई हैं। हमारा आउटपुट या तो true या false होगा, यह दर्शाने के लिए कि क्या हम माचिस वाली लड़की की सभी माचिस की तीलियों का उपयोग करके एक वर्ग बना सकते हैं। इसलिए यदि इनपुट [1,1,2,2,2] है, तो उत्तर true होगा, क्योंकि हम लंबाई 2 का एक वर्ग बना सकते हैं, एक तरफ लंबाई 1 की दो छड़ें होंगी।
हल का दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
solve()नामक एक पुनरावर्ती विधि परिभाषित करें। यहइंडेक्स, sums सरणी, target, और nums सरणीलेगी। यह निम्नानुसार काम करेगा:- यदि
इंडेक्स >= nums आकार, तो:- यदि
sums[0], sum[1] और sum[2] सभी target के समान हैंतो true लौटाएं
- यदि
i = 0 से 3तक:- यदि
sums[i] + nums[इंडेक्स] > target, तो लूप के अगले भाग को छोड़ें sums[i] := sums[i] + nums[इंडेक्स]- यदि
solve(इंडेक्स+1, sums, target, nums)true है, तो true लौटाएं sums[i] := sums[i] - nums[इंडेक्स]
- यदि
- false लौटाएं
- यदि
- मुख्य विधि से, निम्नलिखित करें:
- यदि
nums में कोई तत्व नहीं है, तो false लौटाएं x := 0i = 0 से nums का आकारतक,xकोnums[i]से बढ़ाएं- यदि
x, 4 से विभाज्य है, तो false लौटाएं nums सरणी को क्रमबद्ध करें- आकार 4 की एक सरणी
sumsबनाएं solve(0, sum, x/4, nums)लौटाएं
- यदि
उदाहरण
#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);
}
};
int main(){
vector<int> v = {1,1,2,2,2};
Solution ob;
cout << (ob.makesquare(v));
}
इनपुट
[1,1,2,2,2]
आउटपुट
1