নির্দিষ্ট পজিশনে ওপেনিং ব্র্যাকেট রেখে बैলেন্সড এক্সপ্রেশন গণনা C++-এ

সমস্যা বিবরণ

একটি পূর্ণসংখ্যা n এবং পজিশন অ্যারে 'position[]' (১ <= length <= 2n) দেওয়া আছে। দৈর্ঘ্য 2n-এর প্রপার ব্র্যাকেট এক্সপ্রেশন কতভাবে তৈরি করা যায় যাতে দেওয়া পজিশনগুলোতে ওপেনিং ব্র্যাকেট থাকে।

নোট: position[] অ্যারে ১-বেসড ইনডেক্সিংয়ে দেওয়া হয় [0, 1, 1, 0] রূপে। ১ মানে ওপেনিং ব্র্যাকেট থাকবে, ০ মানে ওপেনিং বা ক্লোজিং যেকোনো একটা হতে পারে।

উদাহরণ

Input: n = 2, position[] = [1, 0, 1, 0] 
Output: 1 
একমাত্র সম্ভাবনা: [ ] [ ]

অ্যালগরিদম

• দেওয়া অ্যারে adj-এ ওপেনিং ব্র্যাকেটের পজিশনগুলো ১ দিয়ে মার্ক করুন।
• রিকার্সিভ লুপ চালান:
  • যদি ওপেনিং মাইনাস ক্লোজিং ব্র্যাকেট কাউন্ট ০-এর চেয়ে কম হয়, ০ রিটার্ন করুন।
  • যদি ইনডেক্স n-এ পৌঁছায় এবং টোটাল ব্র্যাকেট ০ হয়, তবে ১ রিটার্ন করুন (সমাধান পাওয়া গেল), অন্যথায় ০।
  • যদি করেন্ট ইনডেক্সে ১ প্রি-অ্যাসাইনড থাকে, তবে রিকার্সিভ কল করুন index+1 এবং ওপেনিং ব্র্যাকেট কাউন্ট বাড়িয়ে।
  • অন্যথায়, ওপেনিং ব্র্যাকেট রেখে (কাউন্ট+১) এবং ক্লোজিং ব্র্যাকেট রেখে (কাউন্ট-১) দুটো পথে রিকার্সিভ কল করুন।

রিকার্সিভ সমাধান

// C++ application using Recursion 
#include <bits/stdc++.h> 
using namespace std; 

int find(int index1, int openbrk1, int m, int adj1[]) { 
    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; 
    int adj1[4] = {1, 0, 0, 0}; 
    cout << find(0, 0, 2 * m, adj1) << endl; 
    return 0; 
}

আউটপুট

2

মেমোরাইজড অ্যাপ্রোচ

টাইম কমপ্লেক্সিটি অপ্টিমাইজ করতে মেমোরাইজেশন (DP) ব্যবহার করা হয়। dp[index][openbrk] তে রেজাল্ট স্টোর করা হয়।

// C++ application using memorization 
#include <bits/stdc++.h> 
using namespace std; 
#define M 1000 

int find(int index1, int openbrk1, int m, int dp1[M][M], int adj1[]) { 
    if (openbrk1 < 0) return 0; 
    if (index1 == m) { 
        if (openbrk1 == 0) return 1; 
        else return 0; 
    } 
    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() { 
    int dp1[M][M]; 
    int m = 2; 
    memset(dp1, -1, sizeof(dp1)); 
    int adj1[4] = {1, 0, 0, 0}; 
    cout << find(0, 0, 2 * m, dp1, adj1) << endl; 
    return 0; 
}

আউটপুট

2

Time complexity: O(N²)