एक दिए गए पूर्णांक m और स्थितियों की सरणी 'position[]' (1 <= length(position[]) <= 2m) के मामले में, लंबाई 2m के उचित ब्रैकेट अभिव्यक्तियों की संख्या ज्ञात करें जिन्हें बनाया जा सकता है जैसे कि दी गई स्थितियों में ओपनिंग ब्रैकेट हो।
नोट: position[] सरणी (1-आधारित इंडेक्सिंग) के रूप में [0, 1, 1, 0] प्रदान की जाती है। यहां 1 उन स्थितियों को दर्शाता है जहां ओपन ब्रैकेट सेट किया जाना चाहिए। जिन स्थितियों में मान 0 है, वहां ओपनिंग या क्लोजिंग ब्रैकेट सेट किया जा सकता है।
उदाहरण
इनपुट: n = 2, position[] = [1, 0, 1, 0] आउटपुट: 1 एकमात्र संभावना नीचे दी गई है: [ ] [ ] इस मामले में, पुनरावर्ती और मेमोइज़ेशन का उपयोग करने वाला पुनरावर्तन दृष्टिकोण समझाया जाएगा।
एल्गोरिदम
दिए गए सरणी adj1 (मान लें) में ओपन ब्रैकेट वाली सभी स्थितियों को 1 के रूप में चिह्नित करें।
एक पुनरावर्ती लूप इस तरह चलाएं -
यदि कुल ब्रैकेट्स की संख्या (ओपनिंग ब्रैकेट्स को क्लोजिंग ब्रैकेट्स से घटाकर) शून्य से कम है, तो 0 लौटाएं।
यदि इंडेक्स m तक पहुंच जाता है और यदि कुल ब्रैकेट्स 0 के बराबर है, तो एक समाधान उपलब्ध है और 1 लौटाएं, अन्यथा 0 लौटाएं।
यदि इंडेक्स मान को 1 पूर्व-निर्दिष्ट है, तो हमें इंडेक्स+1 के साथ फ़ंक्शन को पुनरावर्ती रूप से लौटाना होगा और कुल ब्रैकेट्स को बढ़ाना होगा।
अन्यथा हमें उस स्थिति या इंडेक्स पर ओपन ब्रैकेट डालकर और कुल ब्रैकेट्स को 1 से बढ़ाकर + उस इंडेक्स पर क्लोज्ड ब्रैकेट डालकर और कुल ब्रैकेट्स को 1 से घटाकर फ़ंक्शन को पुनरावर्ती रूप से लौटाना होगा और m तक अगले इंडेक्स पर जाना होगा।
उपरोक्त एल्गोरिदम के लिए पुनरावर्ती समाधान निम्नानुसार है -
उदाहरण
// पुनरावर्तन का उपयोग करके उपरोक्त विधि का C++ एप्लिकेशन #include <bits/stdc++.h> using namespace std; // उचित ब्रैकेट अभिव्यक्तियों की संख्या खोजने के लिए फ़ंक्शन int find(int index1, int openbrk1, int m, int adj1[]){ // यदि ओपन-क्लोज्ड ब्रैकेट्स 0 से कम if (openbrk1 < 0) return 0; // यदि इंडेक्स अभिव्यक्ति के अंत तक पहुंच जाता है if (index1 == m) { // यदि ब्रैकेट्स संतुलित हैं if (openbrk1 == 0) return 1; else return 0; } // यदि वर्तमान इंडेक्स को ओपन ब्रैकेट असाइन किया गया है if (adj1[index1] == 1) { // हमें ओपन ब्रैकेट्स की लंबाई बढ़ाते हुए आगे बढ़ना है return find(index1 + 1, openbrk1 + 1, m, adj1); } else { // हमें उस इंडेक्स पर ओपन और क्लोज्ड दोनों ब्रैकेट डालकर आगे बढ़ना है return find(index1 + 1, openbrk1 + 1, m, adj1) + find(index1 + 1, openbrk1 - 1, m, adj1); } } // ड्राइवर कोड int main(){ int m = 2; // स्थिति 1 पर ओपन ब्रैकेट int adj1[4] = { 1, 0, 0, 0 }; // उत्तर की गणना करने के लिए find फ़ंक्शन कॉल करें cout << find(0, 0, 2 * m, adj1) << endl; return 0; }आउटपुट
2
मेमोइज़्ड दृष्टिकोण - मेमोइज़ेशन को लागू करके उपरोक्त एल्गोरिदम की समय जटिलता में सुधार या अनुकूलन किया जा सकता है।
केवल एक चीज जो करने की आवश्यकता है वह है पिछले पुनरावृत्तियों के परिणामों को संग्रहीत करने के लिए एक सरणी लागू करना ताकि यदि मान पहले से गणना की गई है तो उसी फ़ंक्शन को एक से अधिक बार पुनरावर्ती रूप से कॉल करने की आवश्यकता न हो।
आवश्यक कार्यान्वयन निम्नानुसार है
// मेमोइज़ेशन का उपयोग करके उपरोक्त विधि का C++ एप्लिकेशन #include <bits/stdc++.h> using namespace std; #define M 1000 // उचित ब्रैकेट अभिव्यक्तियों की संख्या खोजने के लिए फ़ंक्शन int find(int index1, int openbrk1, int m, int dp1[M][M], int adj1[]){ // यदि ओपन-क्लोज्ड ब्रैकेट्स 0 से कम है if (openbrk1 < 0) return 0; // यदि इंडेक्स अभिव्यक्ति के अंत तक पहुंच जाता है if (index1 == m) { // यदि ब्रैकेट्स संतुलित हैं if (openbrk1 == 0) return 1; else return 0; } // यदि पहले से dp1 में संग्रहीत है if (dp1[index1][openbrk1] != -1) return dp1[index1][openbrk1]; // यदि वर्तमान इंडेक्स को ओपन ब्रैकेट असाइन किया गया है if (adj1[index1] == 1) { // हमें ओपन ब्रैकेट्स की लंबाई बढ़ाते हुए आगे बढ़ना है dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1); } else { // हमें उस इंडेक्स पर ओपन और क्लोज्ड दोनों ब्रैकेट डालकर आगे बढ़ना है dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1) + find(index1 + 1, openbrk1 - 1, m, dp1, adj1); } // हमें उत्तर लौटाना है return dp1[index1][openbrk1]; } // ड्राइवर कोड int main(){ // उत्तर की पूर्व-गणना के लिए dp1 सरणी int dp1[M][M]; int m = 2; memset(dp1, -1, sizeof(dp1)); // स्थिति 1 पर ओपन ब्रैकेट int adj1[4] = { 1, 0, 0, 0 }; // उत्तर की गणना करने के लिए find फ़ंक्शन कॉल करें cout<< find(0, 0, 2 * m, dp1, adj1) << endl; return 0; } आउटपुट
2
समय जटिलता: O(N2)