Escribe una función para generar todos los n pares posibles de paréntesis balanceados.
Ejemplos:
Input: n=1
Output: {}
Explanation: This the only sequence of balanced
parenthesis formed using 1 pair of balanced parenthesis.
Input : n=2
Output:
{}{}
{{}}
Explanation: This the only two sequences of balanced
parenthesis formed using 2 pair of balanced parenthesis.
Planteamiento: Formar todas las secuencias de subsecuencias de corchetes balanceados con n pares. Entonces hay n corchetes de apertura y n corchetes de cierre.
Entonces la subsecuencia será de longitud 2*n. Hay una idea simple, el i-ésimo carácter puede ser ‘{‘ si y solo si el conteo de ‘{‘ hasta i’th es menor que n y el i-ésimo carácter puede ser ‘}’ si y solo si el conteo de ‘{‘ es mayor que la cuenta de ‘}’ hasta el índice i. Si se siguen estos dos casos, la subsecuencia resultante siempre estará equilibrada.
Así que forma la función recursiva usando los dos casos anteriores.
Algoritmo:
- Cree una función recursiva que acepte una string (s), el recuento de paréntesis de apertura (o) y el recuento de paréntesis de cierre (c) y el valor de n.
- si el valor del corchete de apertura y el corchete de cierre es igual a n, imprima la string y regrese.
- Si el recuento de paréntesis de apertura es mayor que el recuento de paréntesis de cierre, llame a la función recursivamente con los siguientes parámetros String s + «}» , recuento de paréntesis de apertura o , recuento de paréntesis de cierre c + 1 y n.
- Si el recuento de paréntesis de apertura es menor que n, llame a la función recursivamente con los siguientes parámetros String s + «{« , recuento de paréntesis de apertura o + 1 , recuento de paréntesis de cierre c y n.
Implementación:
C++
// c++ program to print all the combinations of balanced
// parenthesis
#include <bits/stdc++.h>
using namespace std;
vector<string> generateParenthesis(int n)
{
vector<string> two;
vector<string> ans;
if (n == 1) {
two.push_back("{}");
return two;
} // Returning vector if n==1
if (n == 2) {
two.push_back("{{}}");
two.push_back("{}{}");
return two;
} // Returning vector if n==2, as these are base cases
two = generateParenthesis(
n - 1); // Recursively calling the function
// Assigning the previous values of vector into the
// present function
for (int i = 0; i < two.size(); i++) {
string buf = "{", bug = "{", bus = "{";
buf = buf + two[i] + "}";
bug = bug + "}" + two[i];
bus = two[i] + bus + "}";
ans.push_back(buf);
ans.push_back(bus);
ans.push_back(bug);
}
// Removing the duplicate as kind of this {}{} remains
// same in either way
ans.pop_back();
return ans;
}
int main()
{
vector<string>
ff; // Vector to store all the combinations
int n = 2;
ff = generateParenthesis(n); // Calling the function
for (int i = 0; i < ff.size(); ++i) {
cout << ff[i] << endl; // Print all the combinations
/* code */
}
}
// this code is contributed by ManjunathSaiVamshi
C
// C program to Print all combinations
// of balanced parentheses
#include <stdio.h>
#define MAX_SIZE 100
void _printParenthesis(int pos, int n, int open, int close);
// Wrapper over _printParenthesis()
void printParenthesis(int n)
{
if (n > 0)
_printParenthesis(0, n, 0, 0);
return;
}
void _printParenthesis(int pos, int n, int open, int close)
{
static char str[MAX_SIZE];
if (close == n) {
printf("%s \n", str);
return;
}
else {
if (open > close) {
str[pos] = '}';
_printParenthesis(pos + 1, n, open, close + 1);
}
if (open < n) {
str[pos] = '{';
_printParenthesis(pos + 1, n, open + 1, close);
}
}
}
// Driver program to test above functions
int main()
{
int n = 3;
printParenthesis(n);
getchar();
return 0;
}
Java
// Java program to print all
// combinations of balanced parentheses
import java.io.*;
class GFG {
// Function that print all combinations of
// balanced parentheses
// open store the count of opening parenthesis
// close store the count of closing parenthesis
static void _printParenthesis(char str[], int pos,
int n, int open,
int close)
{
if (close == n) {
// print the possible combinations
for (int i = 0; i < str.length; i++)
System.out.print(str[i]);
System.out.println();
return;
}
else {
if (open > close) {
str[pos] = '}';
_printParenthesis(str, pos + 1, n, open,
close + 1);
}
if (open < n) {
str[pos] = '{';
_printParenthesis(str, pos + 1, n, open + 1,
close);
}
}
}
// Wrapper over _printParenthesis()
static void printParenthesis(char str[], int n)
{
if (n > 0)
_printParenthesis(str, 0, n, 0, 0);
return;
}
// driver program
public static void main(String[] args)
{
int n = 3;
char[] str = new char[2 * n];
printParenthesis(str, n);
}
}
// Contributed by Pramod Kumar
Python3
# Python3 program to
# Print all combinations
# of balanced parentheses
# Wrapper over _printParenthesis()
def printParenthesis(str, n):
if(n > 0):
_printParenthesis(str, 0,
n, 0, 0)
return
def _printParenthesis(str, pos, n,
open, close):
if(close == n):
for i in str:
print(i, end="")
print()
return
else:
if(open > close):
str[pos] = '}'
_printParenthesis(str, pos + 1, n,
open, close + 1)
if(open < n):
str[pos] = '{'
_printParenthesis(str, pos + 1, n,
open + 1, close)
# Driver Code
n = 3
str = [""] * 2 * n
printParenthesis(str, n)
# This Code is contributed
# by mits.
C#
// C# program to print all
// combinations of balanced parentheses
using System;
class GFG {
// Function that print all combinations of
// balanced parentheses
// open store the count of opening parenthesis
// close store the count of closing parenthesis
static void _printParenthesis(char[] str, int pos,
int n, int open,
int close)
{
if (close == n) {
// print the possible combinations
for (int i = 0; i < str.Length; i++)
Console.Write(str[i]);
Console.WriteLine();
return;
}
else {
if (open > close) {
str[pos] = '}';
_printParenthesis(str, pos + 1, n, open,
close + 1);
}
if (open < n) {
str[pos] = '{';
_printParenthesis(str, pos + 1, n, open + 1,
close);
}
}
}
// Wrapper over _printParenthesis()
static void printParenthesis(char[] str, int n)
{
if (n > 0)
_printParenthesis(str, 0, n, 0, 0);
return;
}
// driver program
public static void Main()
{
int n = 3;
char[] str = new char[2 * n];
printParenthesis(str, n);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to Print
// all combinations of
// balanced parentheses
$MAX_SIZE = 100;
// Wrapper over
// _printParenthesis()
function printParenthesis($str, $n)
{
if($n > 0)
_printParenthesis($str, 0,
$n, 0, 0);
return;
}
// Function that print
// all combinations of
// balanced parentheses
// open store the count of
// opening parenthesis
// close store the count of
// closing parenthesis
function _printParenthesis($str, $pos, $n,
$open, $close)
{
if($close == $n)
{
for ($i = 0;
$i < strlen($str); $i++)
echo $str[$i];
echo "\n";
return;
}
else
{
if($open > $close)
{
$str[$pos] = '}';
_printParenthesis($str, $pos + 1, $n,
$open, $close + 1);
}
if($open < $n)
{
$str[$pos] = '{';
_printParenthesis($str, $pos + 1, $n,
$open + 1, $close);
}
}
}
// Driver Code
$n = 3;
$str=" ";
printParenthesis($str, $n);
// This Code is contributed by mits.
?>
Javascript
<script>
// javascript program to print all
// combinations of balanced parentheses
// Function that print all combinations of
// balanced parentheses
// open store the count of opening parenthesis
// close store the count of closing parenthesis
function _printParenthesis( str , pos , n , open , close)
{
if (close == n)
{
// print the possible combinations
for (let i = 0; i < str.length; i++)
document.write(str[i]);
document.write("<br/>");
return;
}
else
{
if (open > close)
{
str[pos] = '}';
_printParenthesis(str, pos + 1, n, open, close + 1);
}
if (open < n)
{
str[pos] = '{';
_printParenthesis(str, pos + 1, n, open + 1, close);
}
}
}
// Wrapper over _printParenthesis()
function printParenthesis( str , n)
{
if (n > 0)
_printParenthesis(str, 0, n, 0, 0);
return;
}
// Driver program
var n = 3;
var str = new Array(2 * n);
printParenthesis(str, n);
// This code is contributed by shikhasingrajput
</script>
Producción
{{}}
{}{}
Veamos la implementación del mismo algoritmo de una manera ligeramente diferente, simple y concisa:
C++
// c++ program to print all the combinations of balanced
// parenthesis.
#include <bits/stdc++.h>
using namespace std;
// function which generates all possible n pairs of balanced
// parentheses. open : count of the number of open
// parentheses used in generating the current string s. close
// : count of the number of closed parentheses used in
// generating the current string s. s : currently generated
// string/ ans : a vector of strings to store all the valid
// parentheses.
void generateParenthesis(int n, int open, int close,
string s, vector<string>& ans)
{
// if the count of both open and close parentheses
// reaches n, it means we have generated a valid
// parentheses. So, we add the currently generated string
// s to the final ans and return.
if (open == n && close == n) {
ans.push_back(s);
return;
}
// At any index i in the generation of the string s, we
// can put an open parentheses only if its count until
// that time is less than n.
if (open < n) {
generateParenthesis(n, open + 1, close, s + "{",
ans);
}
// At any index i in the generation of the string s, we
// can put a closed parentheses only if its count until
// that time is less than the count of open parentheses.
if (close < open) {
generateParenthesis(n, open, close + 1, s + "}",
ans);
}
}
int main()
{
int n = 3;
// vector ans is created to store all the possible valid
// combinations of the parentheses.
vector<string> ans;
// initially we are passing the counts of open and close
// as 0, and the string s as an empty string.
generateParenthesis(n, 0, 0, "", ans);
// Now, here we print out all the combinations.
for (auto s : ans) {
cout << s << endl;
}
return 0;
}
Java
// Java program to print all the combinations of balanced
// parenthesis.
import java.util.*;
class GFG {
// function which generates all possible n pairs of
// balanced parentheses.
// open : count of the number of open parentheses used
// in generating the current string s. close : count of
// the number of closed parentheses used in generating
// the current string s. s : currently generated string/
// ans : a vector of strings to store all the valid
// parentheses.
public static void
generateParenthesis(int n, int open, int close,
String s, ArrayList<String> ans)
{
// if the count of both open and close parentheses
// reaches n, it means we have generated a valid
// parentheses. So, we add the currently generated
// string s to the final ans and return.
if (open == n && close == n) {
ans.add(s);
return;
}
// At any index i in the generation of the string s,
// we can put an open parentheses only if its count
// until that time is less than n.
if (open < n) {
generateParenthesis(n, open + 1, close, s + "{",
ans);
}
// At any index i in the generation of the string s,
// we can put a closed parentheses only if its count
// until that time is less than the count of open
// parentheses.
if (close < open) {
generateParenthesis(n, open, close + 1, s + "}",
ans);
}
}
public static void main(String[] args)
{
int n = 3;
// vector ans is created to store all the possible
// valid combinations of the parentheses.
ArrayList<String> ans = new ArrayList<>();
// initially we are passing the counts of open and
// close as 0, and the string s as an empty string.
generateParenthesis(n, 0, 0, "", ans);
// Now, here we print out all the combinations.
for (String s : ans) {
System.out.println(s);
}
}
}
// This code is contributed by ninja_hattori
Python3
# Python program to print all the combinations of balanced parenthesis.
# function which generates all possible n pairs of balanced parentheses.
# open : count of the number of open parentheses used in generating the current string s.
# close : count of the number of closed parentheses used in generating the current string s.
# s : currently generated string/
# ans : a vector of strings to store all the valid parentheses.
def generateParenthesis(n, Open, close, s, ans):
# if the count of both open and close parentheses reaches n, it means we have generated a valid parentheses.
# So, we add the currently generated string s to the final ans and return.
if(Open == n and close == n):
ans.append(s)
return
# At any index i in the generation of the string s, we can put an open parentheses only if its count until that time is less than n.
if(Open < n):
generateParenthesis(n, Open+1, close, s+"{", ans)
# At any index i in the generation of the string s, we can put a closed parentheses only if its count until that time is less than the count of open parentheses.
if(close < Open):
generateParenthesis(n, Open, close + 1, s+"}", ans)
n = 3
# ans is created to store all the possible valid combinations of the parentheses.
ans = []
# initially we are passing the counts of open and close as 0, and the string s as an empty string.
generateParenthesis(n, 0, 0, "", ans)
# Now, here we print out all the combinations.
for s in ans:
print(s)
# This code is contributed by ninja_hattori.
C#
// C# program to print all the combinations of balanced
// parenthesis.
using System;
using System.Collections;
public class GFG {
// function which generates all possible n pairs of
// balanced parentheses.
// open : count of the number of open parentheses used
// in generating the current string s. close : count of
// the number of closed parentheses used in generating
// the current string s. s : currently generated string/
// ans : a vector of strings to store all the valid
// parentheses.
static public void generateParenthesis(int n, int open,
int close,
string s,
ArrayList ans)
{
// if the count of both open and close parentheses
// reaches n, it means we have generated a valid
// parentheses. So, we add the currently generated
// string s to the final ans and return.
if (open == n && close == n) {
ans.Add(s);
return;
}
// At any index i in the generation of the string s,
// we can put an open parentheses only if its count
// until that time is less than n.
if (open < n) {
generateParenthesis(n, open + 1, close, s + "{",
ans);
}
// At any index i in the generation of the string s,
// we can put a closed parentheses only if its count
// until that time is less than the count of open
// parentheses.
if (close < open) {
generateParenthesis(n, open, close + 1, s + "}",
ans);
}
}
static public void Main()
{
// Code
int n = 3;
// vector ans is created to store all the possible
// valid combinations of the parentheses.
ArrayList ans = new ArrayList();
// initially we are passing the counts of open and
// close as 0, and the string s as an empty string.
generateParenthesis(n, 0, 0, "", ans);
// Now, here we print out all the combinations.
for (int i = 0; i < ans.Count; i++) {
Console.WriteLine(ans[i]);
}
}
}
// This code is contributed by ninja_hattori.
Javascript
<script>
// JavaScript program to print all the combinations of balanced parenthesis.
// function which generates all possible n pairs of balanced parentheses.
// open : count of the number of open parentheses used in generating the current string s.
// close : count of the number of closed parentheses used in generating the current string s.
// s : currently generated string/
// ans : an array of strings to store all the valid parentheses.
function generateParenthesis(n, open, close, s, ans)
{
// if the count of both open and close parentheses reaches n, it means we have generated a valid parentheses.
// So, we add the currently generated string s to the final ans and return.
if(open == n && close == n){
ans.push(s);
return;
}
// At any index i in the generation of the string s, we can put an open parentheses only if its count until that time is less than n.
if(open < n)
{
generateParenthesis(n, open + 1, close, s + "{", ans);
}
// At any index i in the generation of the string s, we can put a closed parentheses only if its count until that time is less than the count of open parentheses.
if(close < open)
{
generateParenthesis(n, open, close + 1, s + "}", ans);
}
}
// Driver code
let n = 3;
// array of strings ans is created to store all the possible valid combinations
// of the parentheses.
let ans = [];
// initially we are passing the counts of open and close as 0,
// and the string s as an empty string.
generateParenthesis(n, 0, 0, "", ans);
// Now, here we print out all the combinations.
for(let i = 0; i < ans.length; i++)
{
document.write(ans[i]);
}
// This code is contributed by shinjanpatra
</script>
Producción
{{{}}}
{{}{}}
{{}}{}
{}{{}}
{}{}{}
Gracias a Shekhu por proporcionar el código anterior.
Análisis de Complejidad:
- Complejidad temporal: O(2^n).
Para cada índice puede haber dos opciones ‘{‘ o ‘}’. Entonces se puede decir que el límite superior de la complejidad del tiempo es O(2^n) o tiene una complejidad del tiempo exponencial. - Complejidad espacial: O(n).
La complejidad del espacio se puede reducir a O(n) si se usa una variable global o una variable estática para almacenar la string de salida.
Escriba comentarios si encuentra que los códigos/algoritmos anteriores son incorrectos o encuentra mejores formas de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA