Tutorialspoint.dev

Balanced expressions such that given positions have opening brackets

Given an integer n and an array of positions ‘position[]’ (1 <= position[i] <= 2n), find the number of ways of proper bracket expressions that can be formed of length 2n such that given positions have opening bracket.

Examples :

Input : n = 3, position[] = [2}
Output : 3 
Explanation : 
The proper bracket sequences of length 6 and 
opening bracket at position 2 are:
[ [ ] ] [ ] 
[ [ [ ] ] ]
[ [ ] [ ] ]

Input : n = 2, position[] = {1, 3}
Output : 1
Explanation: The only possibility is:
[ ] [ ]



Approach : This problem can be solved by Dynamic programming..

Let DPi, j be the number of valid ways of filling the first i positions such that there are j more brackets of type ‘[‘ than of type ‘]’. Valid ways would mean that it is the prefix of a matched bracket expression and that the locations at which enforced ‘[‘ brackets are enforced, have been satisfied. It is easy to see that DP2N, 0 is the final answer.

The base case of the DP is, DP0, 0=1. We need to fill the first position with a ‘[‘ bracket, and there is only way to do this.

If the position has a opening bracket sequence which can be marked by a hash array, then the recurrence occurs as :

if(j != 0) dpi, j = dpi-1, j-1
else  dpi, j =  0; 

If the position has no opening bracket sequence, then recurrence happens as :

if(j != 0) dpi, j = dpi - 1, j - 1 + dpi - 1, j + 1
 else  dpi, j = dpi - 1, j + 1

The answer will be DP2n, 0

Given below is the implementation of the above approach :

C++

// CPP code to find number of ways of
// arranging bracket with proper expressions
#include <bits/stdc++.h>
using namespace std;
  
#define N 1000
  
// function to calculate the number
// of proper bracket sequence
long long arrangeBraces(int n, int pos[], int k)
{
  
    // hash array to mark the
    // positions of opening brackets
    bool h[N];
  
    // dp 2d array
    int dp[N][N];
  
    memset(h, 0, sizeof h);
    memset(dp, 0, sizeof dp);
  
    // mark positions in hash array
    for (int i = 0; i < k; i++)
        h[pos[i]] = 1;
  
    // first position marked as 1
    dp[0][0] = 1;
  
    // iterate and formulate the recurrences
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 0; j <= 2 * n; j++) {
  
            // if position has a opening bracket
            if (h[i]) {
                if (j != 0)
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = 0;
            }
            else {
                if (j != 0)
                    dp[i][j] = dp[i - 1][j - 1] +
                               dp[i - 1][j + 1];
                else
                    dp[i][j] = dp[i - 1][j + 1];
            }
        }
    }
  
    // return answer
    return dp[2 * n][0];
}
  
// driver code
int main()
{
    int n = 3;
  
    // positions where opening braces
    // will be placed
    int pos[] = { 2 };
    int k = sizeof(pos)/sizeof(pos[0]);
  
    cout << arrangeBraces(n, pos, k);
    return 0;
}

Java

// Java code to find number of ways of 
// arranging bracket with proper expressions 
  
public class GFG {
  
    static final int N = 1000;
  
// function to calculate the number 
// of proper bracket sequence 
    static long arrangeBraces(int n, int pos[], int k) {
  
        // hash array to mark the 
        // positions of opening brackets 
        boolean h[] = new boolean[N];
  
        // dp 2d array 
        int dp[][] = new int[N][N];
  
        // mark positions in hash array 
        for (int i = 0; i < k; i++) {
            h[pos[i]] = true;
        }
  
        // first position marked as 1 
        dp[0][0] = 1;
  
        // iterate and formulate the recurrences 
        for (int i = 1; i <= 2 * n; i++) {
            for (int j = 0; j <= 2 * n; j++) {
  
                // if position has a opening bracket 
                if (h[i]) {
                    if (j != 0) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        dp[i][j] = 0;
                    }
                } else if (j != 0) {
                    dp[i][j] = dp[i - 1][j - 1]
                            + dp[i - 1][j + 1];
                } else {
                    dp[i][j] = dp[i - 1][j + 1];
                }
            }
        }
  
        // return answer 
        return dp[2 * n][0];
    }
// Driver code 
  
    public static void main(String[] args) {
        int n = 3;
  
        // positions where opening braces 
        // will be placed 
        int pos[] = {2};
        int k = pos.length;
        System.out.print(arrangeBraces(n, pos, k));
    }
}
// This code is contributed by 29AjayKumar

Python3

# Python 3 code to find number of ways of 
# arranging bracket with proper expressions 
N = 1000
  
# function to calculate the number 
# of proper bracket sequence 
def arrangeBraces(n, pos, k):
      
    # hash array to mark the 
    # positions of opening brackets 
    h = [False for i in range(N)] 
  
    # dp 2d array 
    dp = [[0 for i in range(N)]
             for i in range(N)] 
  
    # mark positions in hash array 
    for i in range(k): 
        h[pos[i]] = 1
  
    # first position marked as 1 
    dp[0][0] = 1
  
    # iterate and formulate the recurrences 
    for i in range(1, 2 * n + 1):
        for j in range(2 * n + 1):
              
            # if position has a opening bracket 
            if (h[i]): 
                if (j != 0): 
                    dp[i][j] = dp[i - 1][j - 1
                else:
                    dp[i][j] = 0
            else:
                if (j != 0): 
                    dp[i][j] = (dp[i - 1][j - 1] +
                                dp[i - 1][j + 1])
                else:
                    dp[i][j] = dp[i - 1][j + 1]
                      
    # return answer 
    return dp[2 * n][0]
  
# Driver Code 
n = 3
  
# positions where opening braces 
# will be placed 
pos = [ 2 ,]; 
k = len(pos) 
print(arrangeBraces(n, pos, k))
  
# This code is contributed 
# by sahishelangia

C#

// C# code to find number of ways of 
// arranging bracket with proper expressions 
using System; 
    
class GFG 
    static int N = 1000; 
    
    // function to calculate the number 
    // of proper bracket sequence 
    public static long arrangeBraces(int n, int[] pos, int k) 
    
        
        // hash array to mark the 
        // positions of opening brackets 
        bool[] h = new bool[N]; 
        
        // dp 2d array 
        int[,] dp = new int[N,N]; 
        
        for(int i = 0; i < N; i++)
            h[i] = false;
          
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                dp[i,j] = 0;
        
        // mark positions in hash array 
        for (int i = 0; i < k; i++) 
            h[pos[i]] = true
        
        // first position marked as 1 
        dp[0,0] = 1; 
        
        // iterate and formulate the recurrences 
        for (int i = 1; i <= 2 * n; i++) { 
            for (int j = 0; j <= 2 * n; j++) { 
        
                // if position has a opening bracket 
                if (h[i]) { 
                    if (j != 0) 
                        dp[i,j] = dp[i - 1,j - 1]; 
                    else
                        dp[i,j] = 0; 
                
                else
                    if (j != 0) 
                        dp[i,j] = dp[i - 1,j - 1] + 
                                   dp[i - 1,j + 1]; 
                    else
                        dp[i,j] = dp[i - 1,j + 1]; 
                
            
        
        
        // return answer 
        return dp[2 * n,0]; 
    
        
    // driver code 
    static void Main() 
    
        int n = 3; 
          
        // positions where opening braces 
        // will be placed 
        int[] pos = new int[]{ 2 }; 
        int k = pos.Length; 
        
        Console.Write(arrangeBraces(n, pos, k)); 
    }
    //This code is contributed by DrRoot_
}

Output :

3

Time Complexity: O(n^2)
Auxiliary Space: O(n^2)



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter