Backtracking

Backtracking construiește o soluție pas cu pas. La fiecare pas încearcă un candidat; dacă soluția parțială nu mai poate deveni validă, renunță la acea ramură și revine. Pentru șiruri de lungime 2 din valorile 1 și 2 fără repetiție, alegerea inițială 1 permite apoi doar 2; alegerea inițială 2 permite apoi doar 1. Rezultatele sunt $(1,2)$ și $(2,1)$.

Backtracking construiește soluțiile pas cu pas, în ordine: la fiecare nivel $k$ se alege un candidat pentru poziția $k$, iar dacă soluția parțială nu mai poate fi extinsă într-o soluție completă, se renunță la ultima alegere și se încearcă alta (se „revine”). Soluția se reprezintă printr-un vector $x_1,\dots ,x_n$. Condițiile interne sunt restricțiile pe care trebuie să le respecte o soluție completă; condițiile de continuare verifică dacă soluția parțială $x_1,\dots ,x_k$ poate fi extinsă, deci permit tăierea ramurilor fără soluții înaintea explorării lor. O condiție de continuare corectă respinge numai soluții parțiale care nu pot fi completate, deci nu pierde soluții valide. Spațiul de căutare se poate reprezenta ca un arbore, în care fiecare nod este o soluție parțială și fiecare frunză o soluție completă sau o ramură întreruptă. Ordinea în care sunt încercați candidații determină ordinea în care sunt generate soluțiile. Lecțiile „Backtracking iterativ” și „Backtracking recursiv” arată cele două forme de implementare, iar lecțiile despre permutări, aranjamente, combinări, submulțimi și produs cartezian arată problemele clasice.

Exemplul 1 — șiruri fără repetiție. Pe nivelul 1 se încearcă 1, apoi nivelul 2 poate primi doar 2 (valoarea 1 este deja folosită): rezultă $(1,2)$. După revenire, nivelul 1 încearcă 2, iar nivelul 2 poate primi doar 1: rezultă $(2,1)$. Un fragment cu cicluri imbricate explorează același spațiu mic:

#include <iostream>
using namespace std;
int main() {
    for (int a = 1; a <= 2; ++a)
        for (int b = 1; b <= 2; ++b)
            if (a != b)
                cout << a << b << " ";
    return 0;
}

Programul afișează 12 21. Ciclurile imbricate funcționează numai pentru o lungime fixă, cunoscută la scrierea programului; backtracking-ul gestionează un număr variabil de niveluri prin același mecanism de avans și revenire.

Exemplul 2 — condiție de continuare. Se cer șirurile de 3 cifre din $\{1,2,3\}$ în care două cifre vecine sunt diferite. La nivelul $k$, un candidat $c$ este acceptat numai dacă $c\ne x_{k-1}$; această verificare se face înainte de a trece la nivelul următor, nu la sfârșit. Primul nivel are 3 candidați, iar fiecare dintre nivelurile următoare are câte 2, deci soluțiile sunt $3\cdot 2\cdot 2=12$. Fără tăiere s-ar fi generat $3^3=27$ de șiruri și s-ar fi filtrat la final; cu tăiere, ramurile invalide nu mai sunt explorate.

Vectorul soluție și condițiile. O soluție se scrie ca un vector $x_1,x_2,\dots$, iar fiecare poziție primește valori dintr-o mulțime finită, de obicei $1\dots n$. Pentru poziția $k$ încerci, pe rând, toate valorile posibile și verifici după fiecare condițiile de continuare. Dacă ele sunt îndeplinite și soluția e completă, o afișezi; dacă nu e completă, treci la poziția $k+1$. Dacă nu sunt îndeplinite, încerci valoarea următoare. Când s-au terminat valorile pentru poziția $k$, revii la poziția $k-1$, care trece la următoarea ei valoare: acesta este pasul „înapoi” care dă numele metodei.

Schema recursivă a generării este:

void back(int k) {
    for (int v = 1; v <= n; v++) {
        x[k] = v;
        if (valid(k)) {               // conditiile de continuare
            if (k == n)
                afiseaza();           // solutie completa
            else
                back(k + 1);          // completez pozitia urmatoare
        }
    }
}

Apelul inițial este back(1). Revenirea se face singură: când bucla for de la nivelul $k$ se termină, apelul back(k) se încheie și execuția continuă în bucla de la nivelul $k-1$, cu valoarea următoare. Programa admite și forma iterativă, cu o variabilă $k$ care crește la avans și scade la revenire.

Ordinea soluțiilor. Cu valorile încercate crescător, soluțiile apar în ordine lexicografică, ca într-un dicționar. Pentru permutările lui {1, 2, 3}: 123, 132, 213, 231, 312, 321. La Bacalaureat se cere des soluția care urmează după unele date: o găsești modificând cea mai din dreapta poziție care mai poate primi o valoare mai mare și completând apoi pozițiile de după ea cu cele mai mici valori permise.

Cât durează. Backtracking-ul încearcă, în cel mai rău caz, toate combinațiile de valori, de aceea timpul crește exponențial cu $n$. Condițiile bune de continuare taie devreme ramurile fără soluții. Numărul de soluții se calculează cu formulele de combinatorică: 6 permutări pentru $n=3$, dar 3 628 800 pentru $n=10$.

Exemple suplimentare

Exemplul 3 — ordinea candidaților. Pentru permutările mulțimii $\{1,2,3\}$, dacă pe fiecare nivel candidații sunt încercați în ordine crescătoare, soluțiile apar în ordinea 123, 132, 213, 231, 312, 321. Dacă se încearcă în ordine descrescătoare, prima soluție este 321. Mulțimea soluțiilor este aceeași, dar ordinea afișării diferă.

Exemplul 4 — urmărirea execuției. Se cer șirurile de lungime 3 din valorile 1 și 2 în care două valori vecine sunt diferite. Se pornește cu $x_1=1$. La nivelul 2, candidatul 1 este respins (este egal cu $x_1$), iar candidatul 2 este acceptat. La nivelul 3, candidatul 1 este acceptat, deci se obține $(1,2,1)$; candidatul 2 este respins. Nu mai există candidați, deci se revine la nivelul 1 și se încearcă $x_1=2$, de unde rezultă $(2,1,2)$. Soluțiile sunt două. Pe parcurs s-au testat 10 candidați, dintre care 6 au fost acceptați; fără tăiere s-ar fi generat $2^3=8$ șiruri complete.

Exemple rezolvate

Exemplul 1: permutările. Generează toate permutările mulțimii {1, 2, 3}.

#include <iostream>
using namespace std;

int x[10], n;

int valid(int k) {
    for (int i = 1; i < k; i++)
        if (x[i] == x[k])
            return 0;
    return 1;
}

void afiseaza() {
    for (int i = 1; i <= n; i++)
        cout << x[i];
    cout << "\n";
}

void back(int k) {
    for (int v = 1; v <= n; v++) {
        x[k] = v;
        if (valid(k)) {
            if (k == n) afiseaza();
            else back(k + 1);
        }
    }
}

int main() {
    n = 3;
    back(1);
    return 0;
}

Programul afișează cele $3!=6$ permutări, în ordine lexicografică:

123
132
213
231
312
321

Exemplul 2: combinările. Generează submulțimile cu 3 elemente ale lui {1, 2, 3, 4, 5}.

1. O combinare este o submulțime, deci ordinea nu contează. Ca fiecare submulțime să apară o singură dată, o scrii cu elementele în ordine crescătoare.
2. Condiția de continuare devine $x_k>x_{k-1}$; cel mai simplu, pornești bucla direct de la $x_{k-1}+1$.

#include <iostream>
using namespace std;

int x[10], n = 5, p = 3;

void back(int k) {
    for (int v = x[k - 1] + 1; v <= n; v++) {   // x[0] = 0
        x[k] = v;
        if (k == p) {
            for (int i = 1; i <= p; i++)
                cout << x[i];
            cout << " ";
        } else
            back(k + 1);
    }
}

int main() {
    back(1);
    cout << "\n";
    return 0;
}

Programul afișează cele $C_5^3=10$ combinări:

123 124 125 134 135 145 234 235 245 345

Exemplul 3: soluțiile care urmează. Se generează, în ordine crescătoare, numerele de trei cifre distincte formate cu cifrele 1, 3, 5, 7: 135, 137, 153, … Ce număr se generează imediat după 175 și care este ultimul număr generat? Câte numere se generează în total?

1. Este o generare de aranjamente de 4 luate câte 3, cu cifrele încercate în ordinea 1, 3, 5, 7.
2. 175 este ultimul număr care începe cu 1: a doua cifră a ajuns la 7, cea mai mare, iar a treia nu mai poate crește. Soluția următoare schimbă deci prima cifră în 3 și completează celelalte poziții cu cele mai mici cifre libere: 315.
3. Ultima soluție are pe fiecare poziție cea mai mare cifră încă liberă: 753.
4. În total se generează $A_4^3=4\cdot 3\cdot 2=24$ de numere.

#include <iostream>
using namespace std;

int c[] = {1, 3, 5, 7}, x[4], folosit[4], nr = 0, dupa = 0, ultim = 0;

void back(int k) {
    for (int i = 0; i < 4; i++)
        if (folosit[i] == 0) {
            x[k] = c[i];
            folosit[i] = 1;
            if (k == 3) {
                nr++;
                int v = x[1] * 100 + x[2] * 10 + x[3];
                if (dupa == 1) {         // solutia de imediat dupa 175
                    cout << v << " ";
                    dupa = 0;
                }
                if (v == 175)
                    dupa = 1;
                ultim = v;
            } else
                back(k + 1);
            folosit[i] = 0;          // eliberez cifra la revenire
        }
}

int main() {
    back(1);
    cout << ultim << " " << nr << "\n";
    return 0;
}

Programul afișează soluția de după 175, ultima soluție și numărul total de soluții:

315 753 24

Exemplul 4: submulțimi cu o sumă dată. Câte submulțimi ale mulțimii {2, 3, 5, 7, 8} au suma elementelor egală cu 10?

1. Generezi submulțimile ca șiruri strict crescătoare de poziții și ții suma curentă.
2. Dacă suma depășește 10, nu are rost să continui pe acea ramură (valorile sunt pozitive): aceasta este condiția de continuare.
3. Soluțiile sunt {2, 8}, {3, 7} și {2, 3, 5}: 3 submulțimi.

#include <iostream>
using namespace std;

int a[] = {0, 2, 3, 5, 7, 8}, n = 5, S = 10, x[6], nr = 0;

void back(int k, int suma) {
    for (int i = x[k - 1] + 1; i <= n; i++)
        if (suma + a[i] <= S) {           // altfel ramura nu poate da solutii
            x[k] = i;
            if (suma + a[i] == S) {
                nr++;
                for (int j = 1; j <= k; j++)
                    cout << a[x[j]] << " ";
                cout << "\n";
            } else
                back(k + 1, suma + a[i]);
        }
}

int main() {
    back(1, 0);
    cout << nr << "\n";
    return 0;
}

Programul afișează:

2 3 5
2 8
3 7
3

Soluțiile apar în ordinea generării: întâi toate cele care încep cu 2.

Exemplul 5: nivel de examen, problema celor $n$ regine. Pe o tablă de șah $n\times n$ se așază $n$ regine, astfel încât oricare două să nu se atace: nu sunt pe aceeași linie, aceeași coloană sau aceeași diagonală. Câte așezări există pentru $n=6$?

1. Pe fiecare linie stă exact o regină, deci $x_k$ este coloana reginei de pe linia $k$.
2. Condițiile de continuare: $x_k\ne x_i$ (coloane diferite) și $|x_k-x_i|\ne k-i$ (diagonale diferite), pentru orice $i<k$.
3. Pentru $n=6$ există 4 așezări; pentru $n=4$ există 2, iar pentru $n=8$, 92.

#include <iostream>
using namespace std;

int x[15], n, nr = 0;

int valid(int k) {
    for (int i = 1; i < k; i++) {
        int d = x[k] - x[i];
        if (d < 0) d = -d;
        if (d == 0 || d == k - i)
            return 0;
    }
    return 1;
}

void back(int k) {
    for (int v = 1; v <= n; v++) {
        x[k] = v;
        if (valid(k)) {
            if (k == n) nr++;
            else back(k + 1);
        }
    }
}

int main() {
    cin >> n;
    back(1);
    cout << nr << "\n";
    return 0;
}

Pentru intrarea 6, programul afișează:

4

La numărarea soluțiilor, stabilește dacă ordinea contează și dacă valorile pot fi repetate: ordinea contează la aranjamente și permutări, nu contează la combinări; repetiția este permisă la produsul cartezian. Condițiile de validitate parțială se testează înainte de a avansa la nivelul următor; condițiile care pot fi evaluate doar pe soluția completă se testează la final. Ordinea afișării depinde de ordinea încercării candidaților. Pentru a număra rezultatele unui program cu restricții, înmulțește numărul de alegeri valide pe fiecare nivel numai dacă acesta nu depinde de alegerile anterioare.

Exemplu în formatul examenului. Câte linii afișează programul de mai jos?

#include <iostream>
using namespace std;
int x[4];
void bt(int k) {
    if (k == 4) {
        cout << x[1] << x[2] << x[3] << "\n";
        return;
    }
    for (int c = 1; c <= 3; ++c)
        if (k == 1 || c != x[k - 1]) {
            x[k] = c;
            bt(k + 1);
        }
}
int main() {
    bt(1);
    return 0;
}

• a) 6
• b) 9
• c) 12
• d) 27

Răspunsul corect este c). Condiția c != x[k - 1] interzice ca două cifre vecine să fie egale. Pe nivelul 1 sunt 3 alegeri, iar pe fiecare dintre nivelurile 2 și 3 rămân câte 2 alegeri, deoarece una dintre cele 3 valori este exclusă: $3\cdot 2\cdot 2=12$ șiruri, deci 12 linii. Varianta d) este numărul tuturor șirurilor de 3 cifre din $\{1,2,3\}$, fără restricție, iar varianta a) ar fi numărul permutărilor.

Al doilea exemplu în formatul examenului. Programul de mai jos generează șiruri strict crescătoare. Care este a patra linie afișată?

#include <iostream>
using namespace std;
int x[3];
void bt(int k) {
    if (k == 3) {
        cout << x[1] << x[2] << "\n";
        return;
    }
    for (int c = (k == 1 ? 1 : x[k - 1] + 1); c <= 4; ++c) {
        x[k] = c;
        bt(k + 1);
    }
}
int main() {
    bt(1);
    return 0;
}

• a) 14
• b) 23
• c) 24
• d) 34

Răspunsul corect este b). Programul afișează, în ordine, 12, 13, 14, 23, 24, 34, adică $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ linii. Pentru $x_1=1$ apar trei linii, iar abia a patra linie începe cu $x_1=2$ și are $x_2=3$.

Unde apare la examen

La Bacalaureatul la informatică, matematică-informatică, programa de examen cuprinde metoda backtracking, iterativă sau recursivă (prezentare generală, probleme de generare, oportunitatea utilizării metodei), și generarea elementelor combinatoriale: permutări, aranjamente, combinări, produs cartezian, submulțimi (anexa 2 la OMECTS 4800/2010). La sesiunea din iunie–iulie 2026, al doilea exercițiu al Subiectului al II-lea (6 puncte) a dat primele cinci seturi generate cu backtracking dintr-o mulțime ordonată, cu o restricție, și a cerut a șasea și a șaptea soluție; exemplul 3 exersează același raționament despre ordinea soluțiilor. Formatul descris este cel din 2026; potrivit proiectului de ordin pentru Bacalaureatul 2027, programa rămâne aceeași.

Pe programa școlară veche, metoda backtracking este la clasa a XI-a, cu implementarea iterativă sau recursivă a generării produsului cartezian, a permutărilor, combinărilor, aranjamentelor și submulțimilor (OMECI 5099/2009).

Greșeli frecvente

• Greșit: o ramură invalidă trebuie completată până la capăt.
  Corect: se oprește când nu mai poate deveni validă.
• Greșit: $(1,2)$ și $(2,1)$ sunt aceeași soluție în orice problemă.
  Corect: depinde dacă ordinea contează.
• Greșit: schimbarea ordinii candidaților nu poate schimba ordinea afișării.
  Corect: o poate schimba; la exercițiile cu „soluția următoare” se folosește ordinea din enunț (de exemplu, ordinea elementelor mulțimii date).
• Greșit: condițiile de continuare se verifică doar când vectorul e complet.
  Corect: verificate doar la final, programul generează toate cele $n^n$ variante și devine mult mai lent; fiecare poziție se verifică imediat ce e completată.
• Greșit: marcajul unei valori folosite rămâne setat după autoapel.
  Corect: vectorul folosit se pune pe 0 după autoapel (exemplul 3); altfel valoarea rămâne blocată pentru soluțiile următoare.
• Greșit: combinările se generează ca aranjamentele.
  Corect: fără condiția $x_k>x_{k-1}$, aceeași submulțime apare de mai multe ori, în ordini diferite.
• Greșit: soluția următoare se găsește schimbând prima poziție.
  Corect: se schimbă cea mai din dreapta poziție care mai are o valoare permisă; pozițiile din stânga ei rămân neschimbate.

Înainte și după

Întrebări frecvente