- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

In case of a given integer m and an array of positions ‘position[]’ (1 <= length(position[]) <= 2m), find the number of ways of proper bracket expressions that can be constructed of length 2m such that given positions have the opening bracket.

Note: position[] array is provided in the form of (1-based indexing) [0, 1, 1, 0]. Here 1 indicates the positions at which open bracket should be set. At positions in case of value 0, either opening or closing bracket can be set.

Input: n = 2, position[] = [1, 0, 1, 0] Output: 1 The only possibility is given below: [ ] [ ] In this case, recursive and recursion implementing memorization approach will be explained.

We have to mark all the positions with open brackets in the given array adj1(say) as 1.

We run a recursive loop, in this way −

If count of total brackets(opening brackets subracted from closing brackets) is smaller than zero, return 0.

If the index attains till m and if the total brackets is equal to 0, then a solution is available and return 1, otherwise return 0.

If the index value has 1 pre-assigned to it, we have to return the function recursively with index+1 and increment the total brackets.

Otherwise we have to return the function recursively by inserting open brackets at that position or index and incrementing total brackets by 1 + inserting closed brackets at that index and decrementing total brackets by 1 and move on to the next index till m.

Following is the Recursive solution in case of above algorithm −

// C++ application of above method implementing Recursion #include <bits/stdc++.h> using namespace std; // Function to locate or find Number of proper bracket expressions int find(int index1, int openbrk1, int m, int adj1[]){ // If open-closed brackets less than 0 if (openbrk1 < 0) return 0; // If index reaches the end of expression if (index1 == m) { // If brackets are balanced if (openbrk1 == 0) return 1; else return 0; } // If the current index has assigned open bracket if (adj1[index1] == 1) { // We have to move forward increasing the // length of open brackets return find(index1 + 1, openbrk1 + 1, m, adj1); } else { // We have to move forward by inserting open as well // as closed brackets on that index return find(index1 + 1, openbrk1 + 1, m, adj1) + find(index1 + 1, openbrk1 - 1, m, adj1); } } // Driver Code int main(){ int m = 2; // Open brackets at position 1 int adj1[4] = { 1, 0, 0, 0 }; // Calling the find function to calculate the answer cout << find(0, 0, 2 * m, adj1) << endl; return 0; }

2

**Memorized Approach −**Time complexity of the above algorithm can be improved or optimized by implementing Memorization.

The only thing to be performed is to implement an array to store the results of previous iterations so that there is no require to recursively call the same function more than once if the value is already computed.

// C++ application of above method implementing memorization #include <bits/stdc++.h> using namespace std; #define M 1000 // Function to locate or find Number of proper bracket expressions int find(int index1, int openbrk1, int m, int dp1[M][M], int adj1[]){ // If open-closed brackets is less than 0 if (openbrk1 < 0) return 0; // If index attains or reaches the end of expression if (index1 == m) { // If brackets are balanced if (openbrk1 == 0) return 1; else return 0; } // If already stored in dp1 if (dp1[index1][openbrk1] != -1) return dp1[index1][openbrk1]; // If the current index has assigned open bracket if (adj1[index1] == 1) { // We have to move forward increasing the length of open brackets dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1); } else { // We have to move forward by inserting open as // well as closed brackets on that index dp1[index1][openbrk1] = find(index1 + 1, openbrk1 + 1, m, dp1, adj1) + find(index1 + 1, openbrk1 - 1, m, dp1, adj1); } // We have to return the answer return dp1[index1][openbrk1]; } // Driver Code int main(){ // dp1 array to precalculate the answer int dp1[M][M]; int m = 2; memset(dp1, -1, sizeof(dp1)); // Open brackets at position 1 int adj1[4] = { 1, 0, 0, 0 }; // We have to call the find function to compute the answer cout<< find(0, 0, 2 * m, dp1, adj1) << endl; return 0; }

2

Time complexity: O(N2)

- Related Questions & Answers
- C++ Balanced expressions such that given positions have opening brackets
- Print the balanced bracket expression using given brackets in C Program
- Count pairs of parentheses sequences such that parentheses are balanced in C++
- Find sub-arrays from given two arrays such that they have equal sum in Python
- How to find all the different combinations of opening and closing brackets from the given number k using C#?
- Maximum subarray size, such that all subarrays of that size have sum less than k in C++
- Maximum subarray size, such that all subarrays of that size have sum less than k in C++ program
- Ways to place items in n^2 positions such that no row/column contains more than one in C++
- What is the role of brackets ([ ]) in JavaScript Regular Expressions?
- Find digits not between the brackets using JavaScript Regular Expressions?
- Ways to paint N paintings such that adjacent paintings don’t have same colors in C++
- C program to remove the brackets from a given input.
- Balanced Prime in C++
- Ways to paint N paintings such that adjacent paintings don’t have same colors in C programming
- Program to check whether different brackets are balanced and well-formed or not in Python

Advertisements