Generarea parantezelor corecte prin backtracking C++

Pentru două perechi de paranteze există două secvențe corecte: (()) și ()(). Nu este suficient ca numărul deschiderilor să fie egal cu numărul închiderilor: )( are aceste numere egale, dar închide o paranteză înainte să o deschidă.

Condiția se verifică pe fiecare prefix

Un prefix este partea de la început a secvenței. În orice prefix, numărul închiderilor nu trebuie să depășească numărul deschiderilor. La final, cele două numere trebuie să fie egale cu n.

Citim 0≤n≤8 și afișăm toate secvențele corecte, câte una pe linie, încercând mai întâi paranteza deschisă. Pentru n=0 există o singură secvență, cea goală, și afișăm o linie goală. Capacitatea de 17 caractere include cele cel mult 16 paranteze și terminatorul nul.

Construim numai prefixe valide

Backtracking este o explorare a alegerilor posibile prin construire și revenire. La fiecare poziție putem adăuga ( numai dacă nu am folosit deja n deschideri. Putem adăuga ) numai dacă există o deschidere neînchisă, adică inchise<deschise.

Nu generăm mai întâi toate textele de lungime 2n pentru a le filtra. Ramurile imposibile sunt oprite imediat. Funcția primește poziția curentă și numărul celor două tipuri de paranteze deja scrise.

Pentru două perechi, secvențele corecte sunt (()) și ()(). Prefixul care începe cu ) este respins imediat, chiar dacă totalurile ar putea deveni egale.Mărește schema ↗

Varianta cu char[]

#include <iostream>
using namespace std;
char s[17]; int n;
void genereaza(int poz,int deschise,int inchise) {
    if(poz==2*n) { s[poz]='\0'; cout << s << '\n'; return; }
    if(deschise<n) { s[poz]='('; genereaza(poz+1,deschise+1,inchise); }
    if(inchise<deschise) { s[poz]=')'; genereaza(poz+1,deschise,inchise+1); }
}
int main() { cin >> n; genereaza(0,0,0); }

Varianta echivalentă cu std::string

Păstrăm aceleași limite și exemple. Șirul clasic rezervă spațiu inclusiv pentru terminatorul nul; obiectul string își gestionează memoria. Indicii caracterelor utile pornesc de la zero în ambele variante.

#include <string>

#include <iostream>
using namespace std;
string s; int n;
void genereaza(int poz,int deschise,int inchise) {
    if(poz==2*n) { cout << s << '\n'; return; }
    if(deschise<n) { s[poz]='('; genereaza(poz+1,deschise+1,inchise); }
    if(inchise<deschise) { s[poz]=')'; genereaza(poz+1,deschise,inchise+1); }
}
int main() { cin >> n; s.assign(2*n,' '); genereaza(0,0,0); }

Revenirea nu cere ștergerea întregului text

După întoarcerea dintr-un apel, următoarea alegere suprascrie s[poz]. Numărătorile sunt parametri transmiși prin valoare, deci fiecare apel își păstrează propriile valori. Caracterele de după poziția curentă nu sunt încă parte din prefixul valid construit.

În varianta char[], scriem terminatorul numai când soluția este completă. În varianta string, lungimea este stabilită la 2n și afișăm toate caracterele construite, fără să adăugăm manual un terminator în text.

O secvență completă are n deschideri și n închideri, deoarece nu putem depăși n deschideri, iar închiderile nu pot depăși deschiderile. Fiecare soluție apare o singură dată, pe ramura alegerilor sale.

Dacă numărul soluțiilor este Cn, afișarea lor cere O(n·Cn) timp. Memoria pentru text și adâncimea apelurilor este O(n). Limita n≤8 păstrează volumul de ieșire potrivit pentru exercițiu.

Exersează

Pentru n=1 obții (). Pentru n=2 obții (()) și ()(). Pentru n=3 trebuie să existe cinci rezultate. Verifică fiecare prefix al lor și explică de ce o ramură care începe cu ) nu este încercată niciodată.

Continuă cu backtracking, recursivitate și reprezentarea textului.

Întrebări frecvente

Cum generez numai secvențe corecte de paranteze?

În backtracking, adaugă o deschidere dacă nu ai folosit toate cele n perechi și o închidere numai dacă există o deschidere neînchisă. Astfel nu construiești prefixe deja invalide.

De ce nu este suficient să pun n deschideri și n închideri?

Ordinea poate fi invalidă: )( are numere egale, dar începe cu o închidere fără pereche. În fiecare prefix, numărul închiderilor trebuie să fie cel mult numărul deschiderilor.

Când este completă o secvență generată?

Când au fost folosite exact n deschideri și n închideri, respectând condiția pentru fiecare prefix. Pentru două perechi, rezultatele sunt (()) și ()().