315
Cerinţa
Se dă un număr natural par n
. Generați toate șirurile de n
paranteze rotunde care se închid corect.
Date de intrare
Fişierul de intrare paranteze.in
conţine pe prima linie numărul n
.
Date de ieşire
Fişierul de ieşire paranteze.out
va conţine pe fiecare linie câte un șir de n
paranteze rotunde care se închid corect. Șirurile vor fi afișate în ordine lexicografică, considerând paranteza deschisa (
mai mică decât paranteza închisă )
.
Restricţii şi precizări
1 ≤ n ≤ 20
, număr natural par
Exemplu
paranteze.in
6
paranteze.out
((())) (()()) (())() ()(()) ()()()
#include <bits/stdc++.h> using namespace std; ifstream cin("paranteze.in"); ofstream cout("paranteze.out"); int n , x[25]; int ok() { int c0 = 0 , c1 = 0; for(int i = 1 ; i <= n ; i++) { if(c0 < c1) return 0; if(x[i] == 0) c0++; else c1++; } if(c0 == c1) return 1; return 0; } void afisare() { for(int i = 1 ; i <= n ; i++) if(x[i] == 0) cout << "("; else cout << ")"; cout << '\n'; } void back(int k) { if(k == n + 1) { if(ok()) afisare(); return; } for(int i = 0; i <= 1; i++) { x[k] = i; back(k + 1); } } int main() { cin >> n; back(1); }
Comentarii