Probleme Rezolvate

Să se genereze toate construcțiile corecte de paranteze ( şi ); n este număr par şi se citeşte de la tastatură. De exemplu, pentru n=6, construcțiile (())() şi ()(()) sunt corecte, iar construcția ())(() nu este corectă. indicație. Se generează funcţiile surjective f:A—B unde A = (1,2,3,...,n) = mulțimea pozițiilor ocupate de paranteze, şi B = (0,1) = mulțimea parantezelor — (=0 şi )=1 — care îndeplinesc următoarele condiţii : > f(1)=0 şi f(n)=1 (expresia începe cu paranteză deschisă şi se termină cu o paranteză închisă). Numărul de valori 0 ale funcţiei şi numărul de valori 1 ale funcţiei sunt egale cu n/2 (numărul de paranteze deschise este egal cu numărul de paranteze închise). În timpul construirii soluţiei , nu trebuie ca numărul de valori 1 ale funcţiei să fie mai mare decât numărul de valori 0 generate până la acel moment (numărul de paranteze închise este întotdeauna cel mult egal cu numărul de paranteze deschise).

# include < iostream >
using namespace std ;
void generateParenthesis ( int n, int open, int close , string s) {
if ( s. size () == 2 * n) {
cout << s << endl ;
return ;
}
if (open < n) {
generateParenthesis (n, open + 1 , close , s + "(" );
}
if ( close < open) {
generateParenthesis (n, open, close + 1 , s + ")" );
}
}
int main () {
int n;
cin >> n;
generateParenthesis (n, 0 , 0 , "" );
return 0 ;
}

Funcția generateParenthesis primește patru argumente: n reprezintă numărul total de perechi de paranteze, open reprezintă numărul de paranteze deschise, close reprezintă numărul de paranteze închise și s reprezintă construcția curentă de paranteze.
În funcție, se verifică mai întâi dacă s-a ajuns la o construcție completă, adică când dimensiunea construcției s este egală cu 2*n . În acest caz, se afișează construcția și se returnează din funcție.
În continuare, se verifică dacă se mai pot adăuga paranteze deschise. Dacă da, se adaugă o paranteză deschisă și se apelează recursiv funcția generateParenthesis cu argumentele actualizate.
Apoi, se verifică dacă se mai pot adăuga paranteze închise. Dacă da, se adaugă o paranteză închisă și se apelează recursiv funcția generateParenthesis cu argumentele actualizate.