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>
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>
2
Complejidad del tiempo : O(N 2 )