Backtracking elementar — încearcă, dă înapoi, repetă

De ce contează?

Ești într-un labirint cu o cretă în mână. La fiecare răscruce alegi un coridor și marchezi pe jos pe unde ai mers. Când dai de un zid, nu te blochezi: te întorci pas cu pas până la ultima răscruce, ștergi marcajul drumului greșit și încerci alt coridor. Așa, fără să sari peste nimic, ajungi să verifici toate drumurile posibile. Backtracking-ul este exact asta: explorezi sistematic, iar când nu mai poți avansa, dai înapoi și încerci altceva.

Ce este backtracking-ul?

Backtracking înseamnă să construiești o soluție pas cu pas, încercând pe rând fiecare opțiune posibilă pentru pasul curent. Când o opțiune duce într-un punct mort (sau ai terminat de construit o soluție completă), dai înapoi — anulezi ultima alegere — și încerci opțiunea următoare. Explorezi astfel toate posibilitățile, fără să ratezi vreuna și fără să repeți.

Construcția folosește un vector global sol[] (soluția curentă) și un parametru poz (adâncimea — pe ce poziție lucrezi acum). Pentru fiecare poziție încerci, una câte una, toate valorile permise.

Schema generală are mereu trei timpi, pentru fiecare opțiune:

ALEGE — pui opțiunea în soluție: sol[poz] = optiune.
CONTINUĂ recursiv — apelezi funcția pentru poziția următoare: genereaza(poz + 1). Restul soluției se completează „mai jos” în recursie.
DEZALEGE (undo) — revii la starea de dinainte de alegere, ca poziția să fie liberă pentru următoarea valoare încercată.

Și, ca la orice recursivitate, ai nevoie de un caz de bază — momentul în care soluția e completă (poz == n) și o afișezi.

Exemplu pas cu pas

Să generăm toate șirurile de lungime 3 cu valori 0 și 1. Lucrăm pe sol[0..2] și încercăm pentru fiecare poziție întâi 0, apoi 1.

Pornim de la poz = 0. Alegem sol[0] = 0 și coborâm la poz = 1:

0	_	_
0	1	2

Am ales sol[0]=0 și coborâm la poziția 1.

La poz = 1 alegem din nou 0, apoi la poz = 2 alegem 0. Acum poz == 3 == n, soluția e completă — afișăm 0 0 0:

0	0	0
0	1	2

poz a ajuns la 3: soluție completă, afișăm 0 0 0.

Acum vine partea-cheie: ne întoarcem la poz = 2, dezalegem și încercăm acolo valoarea 1. Obținem 0 0 1. Mai sus nu mai sunt opțiuni la poz = 2, deci urcăm la poz = 1, dezalegem și încercăm 1:

0	1	_
0	1	2

După ce am terminat ramura sol[1]=0, am dat înapoi și am ales sol[1]=1.

Continuând la fel, obținem pe rând: 0 0 0, 0 0 1, 0 1 0, 0 1 1, apoi (după ce dăm înapoi până la poz = 0 și alegem 1) 1 0 0, ... , 1 1 1. În total 8 șiruri — fiecare combinație, exact o dată.

Implementare C++

Generăm toate șirurile de lungime n cu valori 0/1, recursiv, cu sol[] global.

#include <iostream>
using namespace std;

int n = 3;          // lungimea sirului
int sol[20];        // solutia curenta: sol[0..n-1]

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

void genereaza(int poz) {
    if (poz == n) {             // caz de baza: solutie completa
        afiseaza();
        return;
    }
    for (int v = 0; v <= 1; v++) {  // optiunile pentru pozitia curenta
        sol[poz] = v;           // ALEGE
        genereaza(poz + 1);     // CONTINUA recursiv
        // DEZALEGE: aici nu e nevoie de cod, valoarea se suprascrie
        // la urmatoarea iteratie; vezi ObservationBox pentru cazul general
    }
}

int main() {
    genereaza(0);   // pornim de la pozitia 0
    return 0;       // afiseaza 000 001 010 011 100 101 110 111
}

Pentru submulțimile lui {1, 2, ..., n} schimbi doar interpretarea: sol[i] = 1 înseamnă „elementul i+1 este în submulțime”, sol[i] = 0 înseamnă „nu este”. Cele 8 șiruri de mai sus devin cele 8 submulțimi ale lui {1, 2, 3} (inclusiv mulțimea vidă, șirul 000).

Complexitate

Mărime	Valoare	De ce
Număr de soluții generate	O(2^n)	fiecare poziție are 2 opțiuni, `n` poziții
Apeluri recursive	O(2^n)	arborele de explorare are ~`2^(n+1)` noduri
Adâncimea recursiei	O(n)	o ramură are exact `n` niveluri
Memorie pentru soluție	O(n)	vectorul `sol[]` de lungime `n`

Backtracking-ul este intrinsec exponențial aici: numărul de posibilități crește ca 2^n. De-asta, la probleme mari, ai nevoie de tăiere de ramuri (lecție separată) ca să nu explorezi inutil.

Observația-cheie

Dezalegerea (undo) este esența backtracking-ului: după ce o ramură s-a terminat, trebuie să lași starea exact cum era înainte de alegere, ca ramura următoare să pornească curat. La șiruri 0/1 undo-ul e „gratis” fiindcă sol[poz] = v suprascrie valoarea veche la următoarea iterație. Dar la stări mai bogate (un vector folosit[], o sumă parțială, o piesă pusă pe tablă) trebuie să anulezi explicit ce ai modificat înainte de apelul recursiv — altfel ramurile se „murdăresc” una pe alta.

Greșeli frecvente

Uiți pasul de undo: marchezi ceva (ex. folosit[v] = true) înainte de recursie și nu îl readuci la loc după. Starea rămâne „murdară” și ramurile următoare văd alegeri care nu mai sunt valide.
Lipsește cazul de oprire: nu testezi poz == n, deci recursivitatea coboară la infinit (sau iese în afara vectorului sol[]) și programul crapă.
Modifici soluția după ce ai afișat-o: pui cod care schimbă sol[] în cazul de bază, după afiseaza(), și strici starea pentru ramura părinte la urcare.
Recursie care nu avansează poziția: apelezi genereaza(poz) în loc de genereaza(poz + 1). Adâncimea nu crește, nu atingi niciodată cazul de bază și intri în recursie infinită.

Vizualizare

Urmărește cum construcția coboară alegând valori (ramura crește spre dreapta), atinge o soluție completă, apoi dă înapoi dezalegând ultima opțiune și încearcă alta.

Indiciu

Folosește săgețile ← → ca să pășești prin explorare: → avansează (alegi și cobori sau afișezi o soluție), ← te întoarce (dezalegi și revii la nivelul de sus). Observă că după fiecare soluție completă urmează mereu un pas de „dă înapoi”.

Recapitulare

Backtracking = construiești soluția pas cu pas și, când nu mai poți avansa, dai înapoi și încerci altă opțiune — explorezi sistematic toate posibilitățile.
Schema în trei timpi pentru fiecare opțiune: ALEGE (sol[poz] = v) → CONTINUĂ (genereaza(poz + 1)) → DEZALEGE (anulezi alegerea), plus cazul de bază poz == n.
Dezalegerea ține starea curată între ramuri; complexitatea e exponențială (O(2^n) pentru șiruri/submulțimi), de unde nevoia ulterioară de tăiere de ramuri.