ধরুন একটি ছোট ম্যাচের মেয়ে আছে। এবং আমরা জানি ছোট ম্যাচের মেয়েটির কাছে ঠিক কী ম্যাচস্টিক রয়েছে, আমাদের খুঁজে বের করতে হবে একটি উপায় আমরা সেই সমস্ত ম্যাচস্টিকগুলি ব্যবহার করে একটি বর্গক্ষেত্র তৈরি করতে পারি। আমাদের কোনো লাঠি ভাঙা উচিত নয়, তবে আমরা সেগুলিকে সংযুক্ত করতে পারি এবং প্রতিটি ম্যাচস্টিক অবশ্যই একবার ব্যবহার করতে হবে। আমাদের ইনপুট হবে বেশ কয়েকটি ম্যাচস্টিক যা মেয়েটির লাঠির দৈর্ঘ্যের সাথে উপস্থাপন করা হয়েছে। আমাদের আউটপুট সত্য বা মিথ্যা হবে, আমরা ম্যাচ গার্লের সমস্ত ম্যাচস্টিক ব্যবহার করে একটি বর্গক্ষেত্র তৈরি করতে পারি কিনা তা উপস্থাপন করতে। সুতরাং যদি ইনপুটটি [1,1,2,2,2] এর মত হয়, তবে উত্তরটি সত্য হবে, যেমন আমরা দৈর্ঘ্য 2 এর একটি বর্গ করতে পারি, এক পাশে 1 দৈর্ঘ্যের দুটি লাঠি থাকবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- সলভ() নামক একটি পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন। এটি সূচক, সমষ্টি অ্যারে, লক্ষ্য এবং সংখ্যা অ্যারে নেবে। সুতরাং এটি নিম্নরূপ কাজ করবে -
- যদি সূচক>=সংখ্যার আকার হয়, তাহলে
- সত্য প্রত্যাবর্তন করুন যখন যোগফল[0], যোগফল[1] এবং যোগফল[2] সবগুলোই টার্গারের মতো হয়
- আমি 0 থেকে 3 −
- পরিসরে
- যদি যোগফল[i] + সংখ্যা[সূচক]> টার্গেট হয়, তাহলে লুপের পরবর্তী অংশটি এড়িয়ে যান
- সংখ্যা[i] :=যোগফল[i] + সংখ্যা[সূচক]
- যদি সমাধান (index + 1, sums, target, nums) সত্য হয়, তাহলে সত্য ফেরত দিন
- সংখ্যা[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
