Metoda Backtracking explicată pas cu pas pentru elevii de liceu

Backtracking-ul are reputația de "monstru" printre elevi: pare complicat, are recursivitate, are reveniri și parcă nu înțelegi niciodată exact ce se întâmplă. Vestea bună e că, odată ce prinzi schema, toate problemele de backtracking seamănă între ele. Hai să o desfacem pas cu pas.

Ce este backtracking-ul

Backtracking înseamnă să construiești o soluție pas cu pas, iar atunci când îți dai seama că ai apucat-o pe un drum greșit, te întorci (faci "back") și încerci altă variantă.

Gândește-te că ești într-un labirint. Mergi înainte cât poți. Când ajungi într-o fundătură, te întorci la ultima intersecție și încerci alt coridor. Repeți până găsești ieșirea (sau toate ieșirile). Exact asta face un algoritm de backtracking: explorează toate posibilitățile, dar abandonează din timp variantele care nu pot duce la o soluție validă.

Cuvântul-cheie e alegere. La fiecare pas faci o alegere dintr-un set de opțiuni, mergi mai departe, iar la final anulezi alegerea ca să poți încerca următoarea.

Schema generală pe care o reciclezi mereu

Aproape orice problemă de backtracking se scrie după același tipar. Învață-l o dată și îl vei recunoaște peste tot:

void backtracking(int pas) {
    if (solutie_completa(pas)) {
        afiseaza_solutia();
        return;
    }

    for (auto optiune : optiuni_posibile(pas)) {
        if (este_valida(optiune, pas)) {
            fa_alegerea(optiune, pas);   // adaugi opțiunea
            backtracking(pas + 1);       // mergi mai departe
            anuleaza_alegerea(pas);      // revii (BACK!)
        }
    }
}

Reține cele trei momente magice:

1. Condiția de oprire — când o soluție e gata, o folosești și te oprești.
2. Bucla de opțiuni — încerci pe rând fiecare variantă posibilă.
3. Revenirea — după ce ai explorat o ramură, ștergi alegerea ca tabla să rămână curată pentru următoarea.

Dacă uiți pasul de revenire (anuleaza_alegerea), soluțiile tale se "amestecă" între ele și obții rezultate greșite. 90% din bug-urile de backtracking de la începători vin exact de aici.

Primul exemplu clasic: generarea permutărilor

Să generăm toate permutările numerelor de la 1 la n. Pentru n = 3 vrem să afișăm: 123, 132, 213, 231, 312, 321.

Cum gândim soluția? Construim permutarea poziție cu poziție. Pe fiecare poziție încercăm fiecare număr care nu a fost deja folosit. Folosim un vector folosit ca să marcăm ce numere sunt deja în permutarea curentă.

#include <iostream>
using namespace std;

int n;
int perm[20];      // permutarea în construcție
bool folosit[20];  // folosit[i] = true dacă numărul i e deja plasat

void backtracking(int pas) {
    if (pas > n) {                  // am completat toate pozițiile
        for (int i = 1; i <= n; i++)
            cout << perm[i] << " ";
        cout << "\n";
        return;
    }

    for (int nr = 1; nr <= n; nr++) {
        if (!folosit[nr]) {         // numărul nr e disponibil
            perm[pas] = nr;         // fa alegerea
            folosit[nr] = true;

            backtracking(pas + 1);  // mergi la poziția următoare

            folosit[nr] = false;    // revii: eliberezi numărul
        }
    }
}

int main() {
    cin >> n;
    backtracking(1);
    return 0;
}

Urmărește atent rândul folosit[nr] = false;. Asta e revenirea: după ce am explorat toate permutările care încep cu nr pe poziția curentă, eliberăm numărul ca să-l poată folosi altă ramură. Fără el, ai bloca numerele pentru totdeauna.

Al doilea exemplu: submulțimile unei mulțimi

Aici alegerea e și mai simplă. Pentru fiecare element ai exact două opțiuni: îl iei în submulțime sau nu îl iei. De aceea o mulțime cu n elemente are 2^n submulțimi.

int n;
int inSubmultime[20]; // 1 = elementul e ales, 0 = nu

void submultimi(int pas) {
    if (pas > n) {
        cout << "{ ";
        for (int i = 1; i <= n; i++)
            if (inSubmultime[i])
                cout << i << " ";
        cout << "}\n";
        return;
    }

    inSubmultime[pas] = 0;   // varianta: NU luăm elementul
    submultimi(pas + 1);

    inSubmultime[pas] = 1;   // varianta: luăm elementul
    submultimi(pas + 1);
}

Observă că aici nici nu mai avem nevoie de un for clasic — cele două variante sunt scrise explicit. E tot backtracking, doar că arborele de decizii e binar.

Problema damelor, pe scurt

Problema celor n dame îți cere să așezi n regine pe o tablă de șah n × n astfel încât nicio damă să nu atace altă damă (nici pe linie, nici pe coloană, nici pe diagonale).

Cum gândim? Așezăm câte o damă pe fiecare linie, una singură. Pentru linia curentă încercăm fiecare coloană și verificăm dacă poziția e atacată de damele deja plasate. Dacă e validă, mergem la linia următoare; dacă nu, încercăm altă coloană; dacă nicio coloană nu merge, ne întoarcem la linia anterioară și o mutăm. Pură schemă de backtracking.

Iată o comparație rapidă a celor trei probleme, ca să vezi că sunt aceeași idee îmbrăcată diferit:

Problemă	Ce alegi la fiecare pas	Condiția de validare
Permutări	ce număr pui pe poziția curentă	numărul să nu fie deja folosit
Submulțimi	iei sau nu elementul curent	mereu validă (ambele variante merg)
Problema damelor	pe ce coloană pui dama de pe linie	să nu fie atacată de o damă anterioară

Cum gândești o soluție de backtracking, în 4 întrebări

Înainte să scrii cod, răspunde-ți la aceste întrebări. Te scot din orice blocaj:

• Ce construiesc, pas cu pas? (o permutare, o submulțime, o configurație pe tablă)
• Care sunt opțiunile la fiecare pas? (ce număr, ce coloană, da/nu)
• Cum știu că o opțiune e validă? (regula care elimină variantele proaste)
• Când e soluția completă? (am umplut toate pozițiile / am ajuns la finalul mulțimii)

Dacă ai răspuns la toate patru, practic ai scris deja algoritmul — restul e doar să torni răspunsurile în schema generală de mai sus.

Un sfat de aur: taie ramurile cât mai devreme. Cu cât verifici mai repede că o variantă nu poate duce la o soluție validă, cu atât programul tău e mai rapid. Asta se numește pruning și e diferența dintre o soluție care trece testele și una care dă "Time Limit Exceeded".

Concluzie

Backtracking-ul nu e un monstru — e o rețetă care se repetă: alegi, mergi mai departe, revii. Odată ce ai înțeles permutările, submulțimile și problema damelor, recunoști tiparul în zeci de probleme de la Bac și de la olimpiade.

La ByteSchool lucrezi pe exact acest tip de probleme alături de mentori care au trecut ei înșiși prin olimpiade și concursuri de programare. Te învățăm nu doar să copiezi schema, ci să gândești soluția, ca să poți rezolva singur orice problemă nouă de backtracking îți iese în cale.