বন্ধনীর একটি ভারসাম্যপূর্ণ অভিব্যক্তি হল এমন একটি অভিব্যক্তি যাতে সঠিক ক্রমে সব ধরণের বন্ধনীর জোড়া থাকে। এর মানে হল যে প্রতিটি খোলার বন্ধনীর জন্য বন্ধনীর যথাযথ ক্রমে একটি বন্ধ বন্ধনী রয়েছে যেমন { }৷
অভিব্যক্তি − {([][]{})({}[]{})}
আউটপুট - সুষম
এখন, এই সমস্যায় আমাদের প্রদত্ত বন্ধনীর সংখ্যা থেকে সমস্ত সম্ভাব্য ভারসাম্যপূর্ণ অভিব্যক্তি তৈরি করতে হবে। এবং শর্ত হল যে প্রদত্ত অবস্থানে খোলা বন্ধনী রয়েছে।
এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা n এবং 2n দৈর্ঘ্যের বন্ধনীগুলির অবস্থানের একটি অ্যারে দেওয়া হয়েছে এবং আমাদের 2n দৈর্ঘ্যের ভারসাম্যপূর্ণ অভিব্যক্তির সংখ্যা এমনভাবে খুঁজে বের করতে হবে যাতে ওপেনিং ব্র্যাকেট দ্বারা চিহ্নিত অবস্থানগুলিতে খোলা বন্ধনী থাকে ' {'.
উদাহরণ −
Input : n = 2 , position [1, 0 , 0 , 0].
Output : 2
Explanation : All possible outcomes are : {{}} , {}{}. অ্যালগোরিদম
-
একটি সহ সমস্ত অবস্থানগুলি খোলা বন্ধনী৷
৷ -
নিম্নলিখিত নিয়মগুলি ব্যবহার করে একটি পুনরাবৃত্ত লুপ ব্যবহার করুন,
-
যদি ( খোলা বন্ধনীর সংখ্যা - বন্ধ বন্ধনীর সংখ্যা )> 0 , 0 ফেরত দেয়।
-
n পর্যন্ত লুপ করার পর এবং push এবং pop-এর পর মোট বন্ধনী যদি 0 হয়, তাহলে 1 রিটার্ন করুন অর্থাৎ প্রাপ্ত সমাধান। অন্যথায় 0 ফেরত দিন।
-
যদি এক্সপ্রেশনে 1টি আগে থেকে বরাদ্দ করা থাকে, তাহলে সূচক বাড়ানোর জন্য বারবার কল করুন এবং বন্ধনীর মোট সংখ্যা বাড়ান।
-
অন্যথায় ইনডেক্সের জায়গায় খোলা বন্ধনী ঢোকানোর মাধ্যমে ফাংশনটিকে পুনরাবৃত্তভাবে কল করুন এবং তারপরে এটির জন্য বন্ধ বন্ধনীটি সন্নিবেশ করুন এবং বন্ধনীর মোট সংখ্যা হ্রাস করুন এবং পরবর্তী সূচীতে যান৷
-
প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int find(int index, int openbrk, int n, int expression[]){
if (openbrk < 0)
return 0;
if (index == n){
if (openbrk == 0)
return 1;
else
return 0;
}
if (expression[index] == 1) {
return find(index + 1, openbrk + 1, n, expression);
} else {
return find(index + 1, openbrk + 1, n, expression) + find(index + 1, openbrk - 1, n, expression);
}
}
int main() {
int n = 3;
int expression[6] = { 1, 0, 1, 0, 0, 0};
cout << find(0, 0, 2 * n, expression) <<endl;
return 0;
} 