De ce contează?
Deschide orice dicționar și uită-te cum sunt așezate cuvintele: întâi cele care încep cu „a”, apoi „b”, și așa mai departe; la cuvinte care încep la fel, decide următoarea literă. Nimeni nu rearanjează dicționarul după ce-l tipărește — cuvintele ies în ordine fiindcă au fost scrise literă cu literă, fiecare literă aleasă de la mică la mare. Exact așa ies sortate și soluțiile pe care le generezi prin backtracking: nu le sortezi la final, ci le construiești în ordine.
Ideea-cheie
Ai învățat trei generări — permutări, combinări, submulțimi — și ai văzut de fiecare dată aceeași observație discretă: soluțiile ies „în ordine de dicționar”. Nu e o coincidență, și nu e un al patrulea algoritm. E o consecință a unui singur lucru: ordinea în care încerci candidații la fiecare nivel al recursiei.
Backtracking-ul construiește fiecare soluție pas cu pas și explorează arborele de alegeri în adâncime, de la stânga la dreapta. Dacă la fiecare poziție încerci valorile de la mică la mare, atunci ramurile din stânga țin mereu valorile mai mici. Iar a citi frunzele de la stânga la dreapta înseamnă exact a le citi în ordine lexicografică — ca în dicționar: compari prima poziție, la egalitate treci la a doua, și tot așa.
Dacă la fiecare poziție încerci candidații în ordine crescătoare, atunci:
- prima soluție completă pe care o obții este cea mai mică lexicografic;
- toate soluțiile ies deja sortate, fără niciun pas de sortare la final.
„Ordine crescătoare a candidaților la fiecare nivel” ⟺ „parcurgere stânga→dreapta a arborelui” ⟺ „ordine lexicografică a soluțiilor”. Sunt trei feluri de a spune același lucru.
De ce contează? Pentru că enunțurile de concurs cer foarte des ordinea lexicografică:
„afișați soluțiile în ordine lexicografică”, „care e prima soluție?”, „afișați a k-a
soluție”. Dacă generezi crescător, primești ordinea cerută pe gratis — nu mai ai nevoie să
ții toate soluțiile în memorie ca să le sortezi (ceea ce, la n! permutări sau 2^n
submulțimi, oricum n-ar încăpea). Răspunsul iese corect din prima, în fluxul de generare.