Ce este backtracking-ul?

O metodă care construiește o soluție pas cu pas, încercând toate valorile posibile la fiecare pas și întorcându-se la pasul anterior când nu mai poate continua. Generează toate soluțiile.

Backtracking-ul generează toate soluțiile unei probleme atunci când o soluție este o succesiune de alegeri: toate permutările, toate submulțimile, toate așezările damelor pe tablă.

Construiești soluția pas cu pas. La fiecare pas încerci, pe rând, toate valorile posibile. Dacă valoarea aleasă mai poate duce la o soluție, mergi mai departe. Dacă nu, o abandonezi și încerci următoarea. Când nu mai ai ce încerca la pasul curent, te întorci la pasul anterior, de unde vine și numele.

Schema este mereu aceeași. De la o problemă la alta se schimbă doar condiția de continuare (valid): valori distincte pentru permutări, strict crescătoare pentru combinări, nicio condiție pentru produsul cartezian.

La bac apare în două feluri: la Subiectul I („a câta soluție generată este…”, „câte soluții încep cu…”) și la Subiectul II ca generare descrisă în cuvinte. Soluțiile ies în ordine lexicografică dacă valorile se încearcă crescător, așa că poți răspunde desenând arborele.

Lecțiile Backtracking și Aplicații ale backtracking-ului au schema și tabelul de probleme.

Lecția care merge mai departe: Backtracking