1
1. Schema generala backtracking
Backtracking = tehnica de generare sistematica a solutiilor prin explorarea unui arbore de cautare, cu revenire (backtrack) cand o ramura nu mai poate duce la o solutie valida.
Structura arborelui de cautare (n=3, permutari):
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
Schema generala C++ (pseudocod extins):
backtrack(nivel): construieste solutia pas cu pas- Daca
nivel == n+1: solutie completa → afiseaza - Altfel: incearca toate valorile posibile pentru pozitia
nivel - Daca valoarea e valida: plaseaz-o, apeleaza
backtrack(nivel+1), retrage-o
// Schema generala backtracking (C++) void backtrack(int nivel) { if (conditie_succes(nivel)) { afiseaza_solutia(); return; } for (int val = val_min; val <= val_max; val++) { if (valid(nivel, val)) { plaseaza(nivel, val); // adauga in solutie backtrack(nivel + 1); // avansare retrage(nivel, val); // BACKTRACK propriu-zis } } }
Cei 3 pasi cheie la fiecare nivel:
1. Plaseaza → 2. Avanseaza → 3. Retrage (plasare + retragere = stivuire reversibila)
2
2. Permutari ale multimii {1..n}
O permutare a multimii {1, 2, ..., n} este un sir de lungime n in care fiecare element apare exact o data. Numarul total de permutari = n!
⚡ Implementare C++ — EXCLUSIV INTENSIV
La profilul intensiv-informatica, implementarea in C++ cu vectorul folosit[] si recursie este esentiala pentru BAC.
#include <iostream> #include <vector> using namespace std; int n = 3; vector<int> sol; bool folosit[10]; void backtrack(int nivel) { if (nivel == n + 1) { // solutie completa for (int x : sol) cout << x << " "; cout << "\n"; return; } for (int val = 1; val <= n; val++) { if (!folosit[val]) { // val e disponibila sol.push_back(val); folosit[val] = true; backtrack(nivel + 1); sol.pop_back(); // retragere folosit[val] = false; // retragere } } } int main() { backtrack(1); return 0; }
Output real (compilat g++ -std=c++17, rulat):
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Complexitate: O(n · n!) — n! solutii, fiecare necesita O(n) timp pentru afisare. Numarul total de noduri in arbore (inclusiv interne) este aproximativ e · n! (formula exacta: suma k=0..n din n!/k!).
3
3. Combinari C(n,k) — submultimi de k elemente
Combinarile C(n,k) = numarul de modalitati de a alege k elemente din {1..n} fara a conta ordinea. Formula: C(n,k) = n! / (k! · (n-k)!). Elementele sunt mereu in ordine crescatoare.
#include <iostream> #include <vector> using namespace std; int n = 5, k = 3; vector<int> sol; void combinari(int start, int nivel) { if (nivel == k + 1) { // am ales k elemente for (int x : sol) cout << x << " "; cout << "\n"; return; } // pruning: n-(k-nivel) = ultimul val care mai lasa destule elemente for (int val = start; val <= n - (k - nivel); val++) { sol.push_back(val); combinari(val + 1, nivel + 1); sol.pop_back(); } } int main() { combinari(1, 1); return 0; }
Output real — C(5,3) = 10 combinari:
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
Pruning explicat:
Conditia val <= n - (k - nivel) taie ramuri imposibile: daca mai avem nevoie de (k-nivel) elemente si am ajuns la val, trebuie sa mai existe cel putin (k-nivel-1) elemente dupa val. Altfel ne oprim mai devreme → mai putine apeluri.
Complexitate: O(C(n,k) · k) — mult mai eficient decat permutarile cand k << n.
4
4. Aranjamente A(n,k) — ordinea conteaza
Aranjamentele A(n,k) = numarul de siruri ordonate de k elemente distincte din {1..n}. Formula: A(n,k) = n! / (n-k)! = k! · C(n,k). Nota: permutarile sunt cazul special A(n,n) = n!.
#include <iostream> #include <vector> using namespace std; int n = 4, k = 2; vector<int> sol; bool folosit[10]; void aranjamente(int nivel) { if (nivel == k + 1) { // am ales k elemente for (int x : sol) cout << x << " "; cout << "\n"; return; } for (int val = 1; val <= n; val++) { if (!folosit[val]) { // ca la permutari sol.push_back(val); folosit[val] = true; aranjamente(nivel + 1); sol.pop_back(); folosit[val] = false; } } } int main() { aranjamente(1); return 0; }
Output real — A(4,2) = 12 aranjamente:
1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3
Tabel comparativ:
Tip | Formula | n=4, k=2 | Cod: folosit[]? | Incepe de la? -------------|--------------|----------|------------------|--------------- Permutari | n! | 24 | DA | 1 (mereu) Aranjamente | n!/(n-k)! | 12 | DA | 1 (mereu) Combinari | n!/(k!(n-k)!)| 6 | NU | start (crescator)
5
5. Problema reginelor — N-Queens EXCLUSIV INTENSIV
⚡ Problema clasica BAC — intensiv informatica
Plaseaza n regine pe o tabla n×n astfel incat nicio doua regine sa nu se atace (aceeasi linie, coloana sau diagonala). Fiecare linie contine exact o regina → reprezentam solutia ca un vector de coloane.
#include <iostream> #include <vector> using namespace std; int n = 4; vector<int> col; // col[i] = coloana reginei de pe linia i int solutii = 0; bool valid(int linie, int coloana) { for (int i = 0; i < linie; i++) { if (col[i] == coloana) return false; // aceeasi coloana if (abs(col[i] - coloana) == abs(i - linie)) return false; // aceeasi diagonala } return true; } void queens(int linie) { if (linie == n) { // toate liniile ocupate solutii++; if (solutii == 1) { // afiseaza prima solutie cout << "Solutia 1: "; for (int c : col) cout << c + 1 << " "; cout << "\n"; } return; } for (int c = 0; c < n; c++) { if (valid(linie, c)) { col.push_back(c); queens(linie + 1); col.pop_back(); } } } int main() { queens(0); cout << "Total solutii pentru " << n << "-Queens: " << solutii << "\n"; return 0; }
Output real (compilat g++ -std=c++17, rulat):
Solutia 1: 2 4 1 3 Total solutii pentru 4-Queens: 2
Functia valid() verifica 2 conditii:
col[i] == coloana: aceeasi coloana → conflict|col[i] - coloana| == |i - linie|: pe aceeasi diagonala → conflict
6
6. Subset Sum & Pruning — recapitulare BAC
Subset Sum: din vectorul v[0..n-1], gaseste toate submultimile cu suma = S. La fiecare element decidem: il includem sau nu → arbore binar de decizie cu 2^n frunze maxim.
#include <iostream> #include <vector> using namespace std; int n = 5, S = 7; int v[] = {1, 2, 3, 4, 5}; vector<int> sol; void subset_sum(int idx, int suma_curenta) { if (suma_curenta == S) { // succes cout << "{ "; for (int x : sol) cout << x << " "; cout << "}\n"; return; } // PRUNING: nu mai continuam daca am depasit S sau am epuizat elementele if (idx >= n || suma_curenta > S) return; // Includem v[idx] sol.push_back(v[idx]); subset_sum(idx + 1, suma_curenta + v[idx]); sol.pop_back(); // Excludem v[idx] subset_sum(idx + 1, suma_curenta); } int main() { subset_sum(0, 0); return 0; }
Output real — submultimi din {1,2,3,4,5} cu suma = 7:
{ 1 2 4 }
{ 2 5 }
{ 3 4 }
Complexitati reale (pentru BAC):
- Permutari: O(n!) solutii — creste exploziv (10! = 3.628.800)
- Combinari C(n,k): O(C(n,k)) solutii — mult mai mic cand k e fix
- Aranjamente A(n,k): O(n!/(n-k)!) = A(n,k) solutii
- Subset Sum (fara pruning): O(2^n) — exponential in n
- N-Queens: O(n!) cazul rau, mult redus de pruning
Pruning bun poate reduce O(n!) la practic vizitat — esential la examen pentru n mare.
Regula de aur pentru BAC — cele 4 intrebari:
1. Ce e o "solutie"? -> ce avem in vectorul sol[] cand suntem "gata" 2. Cand e "gata"? -> conditia de succes (nivel == n+1, suma == S, etc.) 3. Ce valori incerc? -> domeniul de valori posibile pentru pozitia curenta 4. Ce e "valid"? -> conditia de compatibilitate cu solutia partiala