La generazione di sequenze di parentesi corrette segue direttamente dal modo in cui viene eseguito il controllo: dobbiamo solo aggiungere nuove parentesi senza violare la correttezza. Questo viene fatto mediante iterazione ricorsiva. Se non lo conosci - BE... ah, no, puoi provare a capire leggendo oltre. Ecco un esempio di codice per un tipo di parentesi:
#include <vettore>
#include <iostream>
utilizzando spazio dei nomi std;
int n; // Mezza lunghezza
vettore<carattere> ans; // La nostra risposta
void rec(int saldo) {
if (ans.size() == 2 * n) { // Se lo fa, allora siamo fatto < /span>
for (int i = 0; i < 2 * n; i++)
cout << ans[i] << " ";
cout << "\n";
}
if (ans.size() + balance + 2 <= n * 2) { // Controlla, noi provvediamo a chiudere la nuova parentesi graffa di apertura
// Ora fai attenzione: non abbiamo bisogno di creare un vettore separato per ogni sequenza
ans.push_back('(');
rec(saldo + 1);
ans.pop_back(); // Per capirlo, devi essere consapevole della ricorsione. Innanzitutto, aggiungiamo una parentesi al vettore, quindi eseguiamo nuovamente tutto questo codice.
// Ovvero, aggiungi di nuovo una parentesi, se possibile.
// E questo accadrà finché non inizieremo a lasciare la ricorsione, cioè finché non raggiungeremo la lunghezza desiderata.
// Quindi le parentesi inizieranno a essere rimosse. Se lo capisci, mi congratulo con te, sei fantastico.
}
if (balance > 0) { // Se possiamo chiudere una parentesi, la chiudiamo.
ans.push_back(')');
rec(saldo - 1);
ans.pop_back();
}
}
int main()
{
cin>> N;
rec(0);
ritorno 0;
}
E ora è il momento delle difficoltà: dovrai scrivere TU STESSO l'algoritmo per diversi tipi di parentesi! Muahahahahahahahahahahahaha!