Dado un número entero n y una array de posiciones ‘posición[]’ (1 <= longitud(posición[]) <= 2n), encuentre el número de formas de expresiones de paréntesis adecuadas que se pueden formar de longitud 2n tal que las posiciones dadas tengan el soporte de apertura.
Nota: la array position[] se proporciona en forma de (indexación basada en 1) [0, 1, 1, 0]. Aquí 1 denota las posiciones en las que deben colocarse corchetes abiertos. En las posiciones con valor 0, se puede colocar tanto el paréntesis de apertura como el de cierre.
Ejemplos :
Entrada : n = 3, posición[] = [0, 1, 0, 0, 0, 0]
Salida : 3
Las secuencias de paréntesis adecuadas de longitud 6 y
paréntesis de apertura en la posición 2 son:
[ [ ] ] [ ]
[ [ [ ] ] ]
[ [ ] [ ] ]Entrada : n = 2, posición[] = [1, 0, 1, 0]
Salida : 1
La única posibilidad es:
[ ] [ ]
El enfoque de programación dinámica de este problema ya se ha discutido aquí . En esta publicación, se discutirá la recursividad y la recursividad usando el enfoque de memorización.
Algoritmo –
- Marque todas las posiciones con corchetes abiertos en la array dada adj como 1.
- Ejecute un ciclo recursivo, tal que –
- Si el recuento del total de paréntesis (los paréntesis de apertura restados de los paréntesis de cierre es menor que cero), devuelve 0.
- Si el índice llega hasta n y si el total de paréntesis = 0, entonces se obtiene una solución y devuelve 1, de lo contrario devuelve 0.
- Si el índice tiene 1 preasignado, devuelve la función recursivamente con índice+1 e incrementa el total de paréntesis.
- De lo contrario, devuelva la función recursivamente insertando corchetes abiertos en ese índice e incrementando el total de corchetes en 1 + insertando corchetes cerrados en ese índice y disminuyendo el total de corchetes en 1 y pasando al siguiente índice hasta n.
A continuación se muestra la solución recursiva para el algoritmo anterior:
C++
// C++ implementation of above
// approach using Recursion
#include <bits/stdc++.h>
using namespace std;
// Function to find Number of
// proper bracket expressions
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
int 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 Recursion
using System;
class GFG
{
// 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()
{
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 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
$n = 2;
// Open brackets at position 1
$adj = array(1, 0, 0, 0);
// Calling the find function to
// calculate the answer
echo 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 answer
document.write(find(0, 0, 2 * n, adj));
// This code is contributed by rag2127
</script>
Producción:
2
Enfoque memorizado: la complejidad del tiempo del algoritmo anterior se puede optimizar mediante el uso de Memorización . Lo único que se debe hacer es usar una array para almacenar los resultados de las iteraciones anteriores para que no haya necesidad de llamar recursivamente a la misma función más de una vez si el valor ya se calculó.
A continuación se muestra la implementación requerida:
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 expressions
int 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 Code
int 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 memoization N = 1000; dp = [[-1 for x in range(N)] for y in range(N)]; # Open brackets at position 1 adj = [ 1, 0, 0, 0 ]; # Function to find Number of proper # bracket expressions def 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 answer n = 2; # Calling the find function to # calculate the answer print(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 expressions
function 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 answer
echo find(0, 0, 2 * $n, $dp, $adj) . "\n";
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript implementation of above
// approach using memoization
let N = 1000;
// Function to find Number
// of proper bracket expressions
function 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
let 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 1
let adj = [ 1, 0, 0, 0 ];
// Calling the find function to
// calculate the answer
document.write(find(0, 0, 2 * n, dp, adj));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2
Complejidad del tiempo : O(N 2 )