# 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:
[ ] [ ]
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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 = 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]; ` `} ` ` `  `// driver code ` `int` `main() ` `{ ` `    ``int` `n = 3; ` ` `  `    ``// positions where opening braces ` `    ``// will be placed ` `    ``int` `pos[] = { 2 }; ` `    ``int` `k = ``sizeof``(pos)/``sizeof``(pos); ` ` `  `    ``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)

## tags:

Dynamic Programming Dynamic Programming