Given an integer n and an array of positions ‘position[]’ (1 <= length(position[]) <= 2n), find the number of ways of proper bracket expressions that can be formed of length 2n such that given positions have the opening bracket.
Note: position[] array is given in the form of (1-based indexing) [0, 1, 1, 0]. Here 1 denotes the positions at which open bracket should be placed. At positions with value 0, either of opening and closing bracket can be placed.
Examples:
Input: n = 3, position[] = [0, 1, 0, 0, 0, 0]
Output: 3
The proper bracket sequences of length 6 and
opening bracket at position 2 are:
[ [ ] ] [ ]
[ [ [ ] ] ]
[ [ ] [ ] ]Input: n = 2, position[] = [1, 0, 1, 0]
Output: 1
The only possibility is:
[ ] [ ]
Dynamic Programming approach of this problem has been already discussed here. In this post, recursive and recursion using memoization approach will be discussed.
Algorithm–
- Mark all the positions with open brackets in the given array adj as 1.
- Run a recursive loop, such that –
- If count of total brackets(opening brackets subtracted from closing brackets is less than zero), return 0.
- If the index reaches till n and if the total brackets=0, then a solution is obtained and return 1, otherwise return 0.
- If the index has 1 pre-assigned to it, return the function recursively with index+1 and increment the total brackets.
- Otherwise Return the function recursively by inserting open brackets at that 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 n.
Below is the Recursive solution for above algorithm:
C++
// C++ implementation of above // approach using Recursion#include <bits/stdc++.h>using namespace std;// Function to find Number of// proper bracket expressionsint find(int index, int openbrk, int n, int adj[]){ // If open-closed brackets < 0 if (openbrk < 0) return 0; // If index reaches the end of expression if (index == n) { // IF brackets are balanced if (openbrk == 0) return 1; else return 0; } // If the current index has assigned open bracket if (adj[index] == 1) { // Move forward increasing the // length of open brackets return find(index + 1, openbrk + 1, n, adj); } else { // Move forward by inserting open as well // as closed brackets on that index return find(index + 1, openbrk + 1, n, adj) + find(index + 1, openbrk - 1, n, adj); }}// Driver Codeint main(){ int n = 2; // Open brackets at position 1 int adj[4] = { 1, 0, 0, 0 }; // Calling the find function to calculate the answer cout << find(0, 0, 2 * n, adj) << endl; return 0;} |
Java
// Java implementation of above // approach using Recursion class Test {// Function to find Number of // proper bracket expressions static int find(int index, int openbrk, int n, int[] adj) { // If open-closed brackets < 0 if (openbrk < 0) { return 0; } // If index reaches the end of expression if (index == n) { // IF brackets are balanced if (openbrk == 0) { return 1; } else { return 0; } } // If the current index has assigned open bracket if (adj[index] == 1) { // Move forward increasing the // length of open brackets return find(index + 1, openbrk + 1, n, adj); } else { // Move forward by inserting open as well // as closed brackets on that index return find(index + 1, openbrk + 1, n, adj) + find(index + 1, openbrk - 1, n, adj); } }// Driver Code public static void main(String[] args) { int n = 2; // Open brackets at position 1 int[] adj = {1, 0, 0, 0}; // Calling the find function to calculate the answer System.out.print(find(0, 0, 2 * n, adj)); }} // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of above # approach using memoizaion N = 1000# Function to find Number # of proper bracket expressions def find(index, openbrk, n, dp, adj): # If open-closed brackets<0 if (openbrk < 0): return 0 # If index reaches the end of expression if (index == n): # If brackets are balanced if (openbrk == 0): return 1 else: return 0 # If already stored in dp if (dp[index][openbrk] != -1): return dp[index][openbrk] # If the current index has assigned # open bracket if (adj[index] == 1): # Move forward increasing the # length of open brackets dp[index][openbrk] = find(index + 1, openbrk + 1, n, dp, adj) else: # Move forward by inserting open as # well as closed brackets on that index dp[index][openbrk] = (find(index + 1, openbrk + 1, n, dp, adj) + find(index + 1, openbrk - 1, n, dp, adj)) # return the answer return dp[index][openbrk]# Driver Code # DP array to precompute the answer dp=[[-1 for i in range(N)] for i in range(N)]n = 2; # Open brackets at position 1 adj = [ 1, 0, 0, 0 ] # Calling the find function to # calculate the answer print(find(0, 0, 2 * n, dp, adj))# This code is contributed by sahishelangia |
C#
// C# implementation of above // approach using Recursionusing System;class GFG{// Function to find Number of// proper bracket expressionsstatic int find(int index, int openbrk, int n, int[] adj){ // If open-closed brackets < 0 if (openbrk < 0) return 0; // If index reaches the end of expression if (index == n) { // IF brackets are balanced if (openbrk == 0) return 1; else return 0; } // If the current index has assigned open bracket if (adj[index] == 1) { // Move forward increasing the // length of open brackets return find(index + 1, openbrk + 1, n, adj); } else { // Move forward by inserting open as well // as closed brackets on that index return find(index + 1, openbrk + 1, n, adj) + find(index + 1, openbrk - 1, n, adj); }}// Driver Codepublic static void Main(){ int n = 2; // Open brackets at position 1 int[] adj = { 1, 0, 0, 0 }; // Calling the find function to calculate the answer Console.WriteLine(find(0, 0, 2 * n, adj));}}// This code is contributed by Akanksha Rai |
PHP
<?php // PHP implementation of above approach// using Recursion// Function to find Number of proper // bracket expressionsfunction find($index, $openbrk, $n, &$adj){ // If open-closed brackets < 0 if ($openbrk < 0) return 0; // If index reaches the end // of expression if ($index == $n) { // IF brackets are balanced if ($openbrk == 0) return 1; else return 0; } // If the current index has assigned // open bracket if ($adj[$index] == 1) { // Move forward increasing the // length of open brackets return find($index + 1, $openbrk + 1, $n, $adj); } else { // Move forward by inserting open as well // as closed brackets on that index return find($index + 1, $openbrk + 1, $n, $adj) + find($index + 1, $openbrk - 1, $n, $adj); }}// Driver Code$n = 2;// Open brackets at position 1$adj = array(1, 0, 0, 0);// Calling the find function to // calculate the answerecho find(0, 0, 2 * $n, $adj) . "\n";// This code is contributed by ita_c?> |
Javascript
<script>// Javascript implementation of above // approach using Recursion // Function to find Number of // proper bracket expressions function find(index, openbrk, n, adj){ // If open-closed brackets < 0 if (openbrk < 0) { return 0; } // If index reaches the end of expression if (index == n) { // IF brackets are balanced if (openbrk == 0) { return 1; } else { return 0; } } // If the current index has // assigned open bracket if (adj[index] == 1) { // Move forward increasing the // length of open brackets return find(index + 1, openbrk + 1, n, adj); } else { // Move forward by inserting open as well // as closed brackets on that index return find(index + 1, openbrk + 1, n, adj) + find(index + 1, openbrk - 1, n, adj); }}// Driver Code let n = 2;// Open brackets at position 1 let adj = [ 1, 0, 0, 0 ];// Calling the find function to // calculate the answerdocument.write(find(0, 0, 2 * n, adj));// This code is contributed by rag2127</script> |
Output:
2
Time complexity O(2^n), where n is the total number of brackets in the expression. Space complexity is O(n), which is the maximum number of recursive calls that can be stored on the call stack.
Memoized Approach: Time complexity of the above algorithm can be optimized by using Memorization. The only thing to be done is to use an array to store the results of previous iterations so that there is no need to recursively call the same function more than once if the value is already calculated.
Below is the required implementation:
C++
// C++ implementation of above // approach using memoization#include <bits/stdc++.h>using namespace std;#define N 1000// Function to find Number// of proper bracket expressionsint find(int index, int openbrk, int n, int dp[N][N], int adj[]){ // If open-closed brackets<0 if (openbrk < 0) return 0; // If index reaches the end of expression if (index == n) { // If brackets are balanced if (openbrk == 0) return 1; else return 0; } // If already stored in dp if (dp[index][openbrk] != -1) return dp[index][openbrk]; // If the current index has assigned open bracket if (adj[index] == 1) { // Move forward increasing the // length of open brackets dp[index][openbrk] = find(index + 1, openbrk + 1, n, dp, adj); } else { // Move forward by inserting open as // well as closed brackets on that index dp[index][openbrk] = find(index + 1, openbrk + 1, n, dp, adj) + find(index + 1, openbrk - 1, n, dp, adj); } // return the answer return dp[index][openbrk];}// Driver Codeint main(){ // DP array to precompute the answer int dp[N][N]; int n = 2; memset(dp, -1, sizeof(dp)); // Open brackets at position 1 int adj[4] = { 1, 0, 0, 0 }; // Calling the find function to calculate the answer cout << find(0, 0, 2 * n, dp, adj) << endl; return 0;} |
Java
// Java implementation of above // approach using memoization public class GFG { static final int N = 1000;// Function to find Number // of proper bracket expressions static int find(int index, int openbrk, int n, int dp[][], int adj[]) { // If open-closed brackets<0 if (openbrk < 0) { return 0; } // If index reaches the end of expression if (index == n) { // If brackets are balanced if (openbrk == 0) { return 1; } else { return 0; } } // If already stored in dp if (dp[index][openbrk] != -1) { return dp[index][openbrk]; } // If the current index has assigned open bracket if (adj[index] == 1) { // Move forward increasing the // length of open brackets dp[index][openbrk] = find(index + 1, openbrk + 1, n, dp, adj); } else { // Move forward by inserting open as // well as closed brackets on that index dp[index][openbrk] = find(index + 1, openbrk + 1, n, dp, adj) + find(index + 1, openbrk - 1, n, dp, adj); } // return the answer return dp[index][openbrk]; }// Driver code public static void main(String[] args) { // DP array to precompute the answer int dp[][] = new int[N][N]; int n = 2; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i][j] = -1; } } // Open brackets at position 1 int adj[] = {1, 0, 0, 0}; // Calling the find function to calculate the answer System.out.print(find(0, 0, 2 * n, dp, adj)); }}// This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of above approach# using memoizationN = 1000;dp = [[-1 for x in range(N)] for y in range(N)]; # Open brackets at position 1adj = [ 1, 0, 0, 0 ];# Function to find Number of proper # bracket expressionsdef find(index, openbrk, n): # If open-closed brackets<0 if (openbrk < 0): return 0; # If index reaches the end of expression if (index == n): # If brackets are balanced if (openbrk == 0): return 1; else: return 0; # If already stored in dp if (dp[index][openbrk] != -1): return dp[index][openbrk]; # If the current index has assigned # open bracket if (adj[index] == 1): # Move forward increasing the # length of open brackets dp[index][openbrk] = find(index + 1, openbrk + 1, n); else: # Move forward by inserting open as # well as closed brackets on that index dp[index][openbrk] = (find(index + 1, openbrk + 1, n) + find(index + 1, openbrk - 1, n)); # return the answer return dp[index][openbrk];# Driver Code# DP array to precompute the answern = 2;# Calling the find function to # calculate the answerprint(find(0, 0, 2 * n));# This code is contributed by mits |
C#
// C# implementation of above // approach using memoization using System;class GFG { static readonly int N = 1000; // Function to find Number // of proper bracket expressions static int find(int index, int openbrk, int n, int [,]dp, int []adj) { // If open-closed brackets<0 if (openbrk < 0) { return 0; } // If index reaches the end of expression if (index == n) { // If brackets are balanced if (openbrk == 0) { return 1; } else { return 0; } } // If already stored in dp if (dp[index,openbrk] != -1) { return dp[index, openbrk]; } // If the current index has assigned open bracket if (adj[index] == 1) { // Move forward increasing the // length of open brackets dp[index, openbrk] = find(index + 1, openbrk + 1, n, dp, adj); } else { // Move forward by inserting open as // well as closed brackets on that index dp[index, openbrk] = find(index + 1, openbrk + 1, n, dp, adj) + find(index + 1, openbrk - 1, n, dp, adj); } // return the answer return dp[index,openbrk]; } // Driver code public static void Main() { // DP array to precompute the answer int [,]dp = new int[N,N]; int n = 2; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { dp[i, j] = -1; } } // Open brackets at position 1 int []adj = {1, 0, 0, 0}; // Calling the find function to calculate the answer Console.WriteLine(find(0, 0, 2 * n, dp, adj)); }}// This code is contributed by PrinciRaj1992 |
PHP
<?php// PHP implementation of above approach// using memoization// Function to find Number of proper // bracket expressionsfunction find($index, $openbrk, $n, &$dp, &$adj){ // If open-closed brackets<0 if ($openbrk < 0) return 0; // If index reaches the end of expression if ($index == $n) { // If brackets are balanced if ($openbrk == 0) return 1; else return 0; } // If already stored in dp if ($dp[$index][$openbrk] != -1) return $dp[$index][$openbrk]; // If the current index has assigned // open bracket if ($adj[$index] == 1) { // Move forward increasing the // length of open brackets $dp[$index][$openbrk] = find($index + 1, $openbrk + 1, $n, $dp, $adj); } else { // Move forward by inserting open as // well as closed brackets on that index $dp[$index][$openbrk] = find($index + 1, $openbrk + 1, $n, $dp, $adj) + find($index + 1, $openbrk - 1, $n, $dp, $adj); } // return the answer return $dp[$index][$openbrk];}// Driver Code// DP array to precompute the answer$N = 1000;$dp = array(array());$n = 2;for ($i = 0; $i < $N; $i++) { for ($j = 0; $j < $N; $j++) { $dp[$i][$j] = -1; }}// Open brackets at position 1$adj = array( 1, 0, 0, 0 );// Calling the find function to // calculate the answerecho find(0, 0, 2 * $n, $dp, $adj) . "\n";// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// Javascript implementation of above// approach using memoizationlet N = 1000;// Function to find Number// of proper bracket expressionsfunction find(index, openbrk, n, dp, adj){ // If open-closed brackets<0 if (openbrk < 0) { return 0; } // If index reaches the end of expression if (index == n) { // If brackets are balanced if (openbrk == 0) { return 1; } else { return 0; } } // If already stored in dp if (dp[index][openbrk] != -1) { return dp[index][openbrk]; } // If the current index has // assigned open bracket if (adj[index] == 1) { // Move forward increasing the // length of open brackets dp[index][openbrk] = find(index + 1, openbrk + 1, n, dp, adj); } else { // Move forward by inserting open as // well as closed brackets on that index dp[index][openbrk] = find(index + 1, openbrk + 1, n, dp, adj) + find(index + 1, openbrk - 1, n, dp, adj); } // Return the answer return dp[index][openbrk];}// Driver code// DP array to precompute the answerlet dp = new Array(N);for(let i = 0; i < N; i++) { dp[i] = new Array(N); for(let j = 0; j < N; j++) { dp[i][j] = -1; }}let n = 2;// Open brackets at position 1let adj = [ 1, 0, 0, 0 ];// Calling the find function to // calculate the answerdocument.write(find(0, 0, 2 * n, dp, adj));// This code is contributed by avanitrachhadiya2155</script> |
Output:
2
Time complexity: O(N2),because we are storing the intermediate results in a 2D array of size NN and we need to compute the value for each cell only once. Space complexity:O(N2), because we are storing the intermediate results in a 2D array of size N*N.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
