Într-un labirint încerci un coridor; dacă e înfundat, te ÎNTORCI la ultima intersecție și încerci următorul.
Backtracking construiește soluțiile element cu element, iar când o alegere nu mai poate duce la nimic bun — o șterge și încearcă alta.
Motorul din spate? Stiva de apeluri de la recursivitate.
🎯 Obiectiv 2Scrii schema generală recursivă în C++ și Python.
🎯 Obiectiv 3Generezi permutări, aranjamente, combinări, produs cartezian — cele patru din programă.
1
Cele patru întrebări — vocabularul metodei
Programa cere exact aceste repere. Răspunde-le la ORICE problemă de Backtracking, înainte să scrii o linie de cod:
① Ce este o soluție?
Un vector sol[1..n] — de exemplu, o permutare completă: sol = (2, 3, 1).
② Ce e un element?
sol[k] — valoarea pusă pe poziția k, aleasă dintr-o mulțime de candidați (1..n).
③ Când e valid sol[k]?
Condiția de continuare — la permutări: sol[k] să NU fi apărut pe pozițiile 1..k−1.
④ Când e completă?
Când k == n: toate pozițiile sunt umplute valid → afișăm soluția.
Legătura cu recursivitatea (X·M10): „merg înainte" = apel bt(k+1) ·
„revin" = întoarcerea din apel, care continuă AUTOMAT bucla candidaților de la nivelul anterior. Stiva de apeluri ține minte drumul — tu nu ții nimic!
2
Laboratorul viu: permutările lui {1, 2, 3}
Înainte de orice cod, vezi PROCESUL: fiecare pas al algoritmului, vizibil. Auriu = încerc, roșu = invalid, albastru = pus, verde = soluție. Numără și revenirile!
apasă Pas — începem cu sol[1] 👆
Citește ritmul: înainte cât se poate, soluție când k = n, înapoi când candidații s-au terminat.
Cele 3! = 6 soluții apar în ordine LEXICOGRAFICĂ — Backtracking-ul generează mereu ordonat, de-asta îl iubește BAC-ul.
3
Schema generală — de unde vine, de fapt
Înainte de cod: de ce arată schema așa? Pornim de la ceva ce știi deja — for-urile imbricate.
💡 Marea idee: backtracking = for-uri imbricate, dar câte nu știm dinainte
Backtracking e, de fapt, matematica de la Permutări, Aranjamente, Combinări pusă pe ecran — afișăm ce numărăm la mate. Să generăm permutările lui {1, 2, 3}. Dacă n = 3, e simplu: trei for-uri unul în altul.
1for (int a = 1; a <= 3; a++) // poziția 1
2 for (int b = 1; b <= 3; b++) // poziția 2
3 for (int c = 1; c <= 3; c++) // poziția 3
4 if (a!=b && a!=c && b!=c) // validarea: distincte
5 cout << a << b << c << '\n'; // o soluție!
Dar dacă n = 5? Ai nevoie de 5 for-uri. Dacă n e citit de la tastatură, oarecare? Nu poți scrie un număr variabil de for-uri în cod! Aici intervine recursivitatea: un subprogram care se autoapelează generează exact n for-uri imbricate — câte unul pentru fiecare poziție a vectorului soluție sol[].
Deci schema de mai jos = for-urile de sus, dar cu n variabil. Fiecare apel bt(k) ESTE un for (bucla de candidați pentru poziția k); apelul bt(k+1) = „intru în for-ul următor"; întoarcerea din apel = „am terminat for-ul, ies un nivel". Metoda e lentă (încearcă tot), dar de multe ori e singura pe care o avem.
🔎 Flowchart + cod + exemplu: permutările lui {1, 2, 3}, pas cu pas
Apasă Pas și urmărește simultan: nodul din organigramă (auriu), linia de cod și starea vectorului sol[]. Așa vezi cum recursivitatea „ține" cele n for-uri.
1bool valid(int k) { // ③ e bună alegerea?
2 for (int i = 1; i < k; i++)
3 if (sol[i] == sol[k]) return false; // repetiție
4 return true;
5}
6void afisare() { // ④ scrie soluția
7 for (int i = 1; i <= n; i++) cout << sol[i];
8 cout << '\n';
9}
10void bt(int k) {
11 for (v = 1; v <= n; v++) {
12 sol[k] = v;
13 if (valid(k)) {
14 if (k == n)
15 afisare(); // soluție!
16 else
17 bt(k + 1); // mai adânc
18 }
19 } // for gata → revin
20}
k = — · v = —
apasă „Pas" — intrăm în bt(1) 👆
Schema recursivă — de învățat ca o poezie
Aceeași schelă pentru toate problemele; se schimbă doar candidații, validarea și afișarea.
1int sol[20], n; // vectorul soluție
2bool valid(int k) { // ③ validare
3 for (int i = 1; i < k; i++)
4 if (sol[i] == sol[k]) return false;
5 return true;
6}
7void afisare() { // ④ scrie soluția
8 for (int i = 1; i <= n; i++) cout << sol[i];
9 cout << '\n';
10}
11void bt(int k) {
12 for (int v = 1; v <= n; v++) { // ② candidații
13 sol[k] = v; // pun elementul
14 if (valid(k)) {
15 if (k == n) afisare(); // ④ completă
16 else bt(k + 1); // înainte!
17 }
18 } // bucla gata → revin
19} // apel din main: bt(1)
1def afisare(sol): # ④ scrie soluția
2 print(*sol)
3def bt(k, sol):
4 for v in range(1, n + 1):
5 if v not in sol: # ③ validare
6 sol.append(v) # pun
7 if len(sol) == n:
8 afisare(sol) # soluție!
9 else:
10 bt(k + 1, sol)# înainte
11 sol.pop() # REVIN: șterg!
12bt(1, [])
Detaliul care pică elevii la BAC: în C++, sol[k] e pur și simplu SUPRASCRIS de următorul candidat —
revenirea e implicită. În Python cu listă, trebuie să ștergi explicit cu sol.pop() după apel. Același dans, coregrafii diferite.
⚡ Altă scriere a lui valid(): cu vector de frecvență
Bucla din valid() costă O(k) la fiecare verificare. Ținem în schimb un vector de frecvență fr[] — fr[v] spune dacă valoarea v e deja folosită — și verificăm în O(1). Marcăm valoarea când o punem și o demarcăm la revenire.
valid clasic — O(k)
1bool valid(int k) {
2 for (int i = 1; i < k; i++)
3 if (sol[i] == sol[k])
4 return false;
5 return true;
6}
valid cu frecvență — O(1)
1bool fr[20]; // fr[v]=1 dacă v e folosit
2bool valid(int k) {
3 return fr[sol[k]] == 0; // e liber?
4}
…dar acum bt() trebuie să întrețină vectorul fr[] — marchează la coborâre, demarchează la revenire:
1void bt(int k) {
2 for (int v = 1; v <= n; v++) {
3 sol[k] = v;
4 if (valid(k)) { // O(1) acum
5 fr[v] = 1; // marchez valoarea folosită
6 if (k == n) afisare();
7 else bt(k + 1);
8 fr[v] = 0; // REVIN: o eliberez
9 }
10 }
11}
De reținut: vectorul de frecvență e trucul standard pentru permutări și aranjamente. În loc să cauți prin tot ce ai pus (O(k)), ții o „bifă" per valoare și răspunzi instant — aceeași idee de marcare/demarcare ca la ciur. Nu uita să demarchezi la revenire, altfel „murdărești" ramurile următoare!
4
Cele patru generări din programă
Aceeași schelă — schimbi DOAR validarea și lungimea soluției. Apasă pe fiecare ca să vezi codul complet C++ și Python:
C++
1int sol[20], n;
2bool valid(int k) {
3 for (int i = 1; i < k; i++)
4 if (sol[i] == sol[k]) return false; // fără repetiție
4 start = 1 if not sol else sol[-1] + 1 # crescător
5 for v in range(start, n + 1):
6 x.append(v)
7 bt(x)
8 x.pop()
9n, K = int(input()), int(input())
10bt([])
C++
1int x[20], n, m;
2void bt(int k) { // nicio validare!
3 for (int v = 1; v <= m; v++) {
4 x[k] = v; // orice valoare, oriunde
5 if (k == n) {
6 for (int i=1;i<=n;i++) cout<<x[i];
7 cout << '\n';
8 } else bt(k + 1);
9 }
10} // cin>>n>>m; bt(1);
Python
1def bt(x):
2 if len(x) == n:
3 print(*x); return
4 for v in range(1, m + 1): # fără validare
5 x.append(v)
6 bt(x)
7 x.pop()
8n, m = int(input()), int(input())
9bt([])
Trucul combinărilor: condiția „strict crescător" omoară dublurile de ordine —
{1,3} și {3,1} sunt aceeași mulțime, deci păstrăm doar varianta crescătoare. O singură condiție, jumătate de muncă.
Cât „costă" explorarea?
n =
5
Verificare rapidă
Cinci întrebări despre schema Backtracking.
6
Fișa de sinteză
Schema Backtracking, condensată.
Cele 4 întrebări: ce e soluția (vector sol) · ce e un element (sol[k]) · când e valid · când e completă (k == n).
Schema: for candidați → pun sol[k] → dacă valid: soluție SAU bt(k+1) → bucla gata = revenire automată.
Revenirea: în C++ suprascrierea, în Python sol.pop() explicit după apel.
Cele 4 generări: permutări (n!, fără repetiție) · aranjamente (lungime k) · combinări (crescător!) · produs cartezian (fără validare, m^n).
Ordinea soluțiilor e lexicografică — candidații se încearcă crescător; întrebarea BAC „a câta soluție este…?" se rezolvă numărând ordonat.
Costul e exponențial — validarea timpurie (pruning) taie ramuri întregi; de-asta validăm la FIECARE nivel, nu la final.
Urmează: punem schema la lucru pe problemele-legendă — reginele, colorarea hărții, partițiile, comis-voiajorul.