ধরুন একটি ছোট মাচলার মেয়ে আছে। এবং আমরা সঠিকভাবে জানি ছোট মাচলার মেয়েটির কী মাচস্টিক আছে, আমাদের একটি উপায় খুঁজে বের করতে হবে যাতে সেই সব মাচস্টিক ব্যবহার করে একটি বর্গ তৈরি করা যায়। আমাদের কোনো স্টিক ভাঙতে পারব না, কিন্তু সেগুলি সংযুক্ত করতে পারব, এবং প্রতিটি মাচস্টিক সঠিকভাবে একবার ব্যবহার করা উচিত। আমাদের ইনপুট হবে মেয়েটির বেশ কিছু মাচস্টিক, তাদের স্টিকের দৈর্ঘ্য দিয়ে প্রতিনিধিত্ব করা। আমাদের আউটপুট হবে true অথবা false, যা প্রতিনিধিত্ব করবে যে কি আমরা মাচলার মেয়েটির সব মাচস্টিক ব্যবহার করে একটি বর্গ তৈরি করতে পারি কিনা। তাই যদি ইনপুট হয় [1,1,2,2,2], তবে উত্তর হবে true, কারণ আমরা দৈর্ঘ্য ২-এর একটি বর্গ তৈরি করতে পারি, একটি পাশে দৈর্ঘ্য ১-এর দুটি স্টিক থাকবে।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- solve() নামে একটি রিকার্সিভ মেথড সংজ্ঞায়িত করুন। এটি index, sums অ্যারে, target এবং nums অ্যারে নেবে। এটি নিম্নরূপ কাজ করবে −
- যদি index >= nums size, তবে
- true ফেরত দিন যখন sums[0], sum[1] এবং sum[2] সব target-এর সমান হয়
- i = 0 থেকে 3 −
- যদি sums[i] + nums[index] > target, তবে লুপের পরবর্তী অংশ স্কিপ করুন
- sums[i] := sums[i] + nums[index]
- যদি solve(index + 1, sums, target, nums) true হয়, তবে true ফেরত দিন
- sums[i] := sums[i] – nums[index]
- false ফেরত দিন
- মূল মেথড থেকে, নিম্নলিখিত কাজ করুন −
- যদি nums-এ কোন উপাদান না থাকে, তবে false ফেরত দিন
- x := 0
- i = 0 থেকে nums-এর আকার পর্যন্ত, x nums[j]-এ যোগ করুন
- যদি x ৪ দ্বারা বিভাজ্য হয়, তবে false ফেরত দিন
- nums অ্যারে সাজান
- ৪ আকারের একটি 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); } }; main(){ vector<int> v = {1,1,2,2,2}; Solution ob; cout << (ob.makesquare(v)); }ইনপুট
[1,1,2,2,2]
আউটপুট
1
