La génération de séquences de parenthèses correctes découle directement de la façon dont la vérification est effectuée - nous avons juste besoin d'ajouter de nouvelles parenthèses sans violer l'exactitude. Cela se fait par itération récursive. Si vous ne le connaissez pas - BE... ah, non, vous pouvez essayer de comprendre en lisant plus loin. Voici un exemple de code pour un type de parenthèse :
#include <vecteur>
#include <iostream>
en utilisant espace de noms std ;
entier n ; // Demi-longueur
vecteur<char> ; répondez ; // Notre réponse
void rec(int balance) {
if (ans.size() == 2 * n) { // Si c'est le cas, alors nous sommes fait < /span>
pour (int i = 0 ; i < 2 * n ; i++)
cout << ans[i] << " ";
cout << "\n" ;
}
if (ans.size() + balance + 2 <= n * 2) { // Vérifie, nous allons faire en sorte que nous fermions la nouvelle accolade ouvrante
// Maintenant faites attention à vos mains : nous n'avons pas besoin de créer un vecteur séparé pour chaque séquence
ans.push_back('(');
rec(solde + 1);
ans.pop_back(); // Pour comprendre cela, vous devez être conscient de la récursivité. Tout d'abord, nous ajoutons une parenthèse au vecteur, puis nous exécutons à nouveau tout ce code.
// Autrement dit, ajoutez à nouveau une parenthèse, si nous le pouvons.
// Et cela se produira jusqu'à ce que nous commencions à quitter la récursivité - c'est-à-dire jusqu'à ce que nous atteignions la longueur souhaitée.
// Ensuite, les crochets commenceront à être supprimés. Si vous comprenez cela - je vous félicite, vous êtes génial.
}
if (balance > 0) { // Si nous pouvons fermer une parenthèse, nous la fermons.
ans.push_back(')');
rec(solde - 1);
ans.pop_back();
}
}
int main()
{
cin>> n;
rec(0);
retour 0 ;
}
Et maintenant, le temps des difficultés - vous devrez écrire vous-même l'algorithme pour plusieurs types de parenthèses ! Muahahahahahahahahahahahah !