Itemii de backtracking de la BAC Informatică au aproape mereu aceeași formă: enunțul descrie o generare, îți dă primele soluții ca exemplu și te întreabă care este soluția de pe o anumită poziție, soluția de după o soluție dată sau câte soluții au o anumită proprietate. Nu trebuie să scrii cod. Trebuie însă să răspunzi repede și corect, iar metoda „le scriu pe toate până ajung acolo” e lentă și plină de ocazii de greșeală. Mai jos ai tehnica pe care o poți aplica la orice astfel de item.
Pasul 0: traduce enunțul în numere
Enunțurile vorbesc despre flori, culori, orașe sau cifre. Primul lucru pe care îl faci este să numerotezi elementele în ordinea în care apar în enunț (1, 2, 3, …) și să stabilești tipul generării:
- ordinea contează și se folosesc toate elementele → permutări;
- ordinea contează, dar se iau doar p elemente → aranjamente;
- ordinea nu contează (grupuri, submulțimi) → combinări, scrise cu indici crescători.
Apoi verifici ipoteza pe soluțiile date ca exemplu. Dacă primele trei soluții se potrivesc cu ce ar produce generarea ta, ai înțeles corect enunțul.
Tehnica „soluției următoare”
Backtracking-ul se comportă ca un contor: modifică întotdeauna cea mai din dreapta poziție care mai poate fi crescută, iar tot ce urmează după ea primește cele mai mici valori valide. De aici rezultă algoritmul de lucru de mână:
- Pornești de la ultima poziție a soluției date.
- Te întrebi: există o valoare mai mare decât cea actuală, care să fie validă ținând cont de elementele din stânga?
- Dacă nu, treci la poziția din stânga și repeți întrebarea.
- La prima poziție unde răspunsul e „da”, pui cea mai mică valoare mai mare care e validă.
- Completezi pozițiile din dreapta cu cele mai mici valori valide, în ordine.
Exemplul 1: permutări
Se generează în ordine lexicografică permutările mulțimii {1, 2, 3, 4}. Care este permutarea generată imediat după 2 4 3 1?
- Poziția 4 (valoarea 1): singura valoare nefolosită de pozițiile 1–3 este chiar 1, deci nu poate crește.
- Poziția 3 (valoarea 3): ar trebui o valoare mai mare decât 3, nefolosită de 2 și 4. Nu există.
- Poziția 2 (valoarea 4): nu există valoare mai mare decât 4.
- Poziția 1 (valoarea 2): poate deveni 3.
- Completezi restul cu cele mai mici valori nefolosite: 1, 2, 4.
Răspuns: 3 1 2 4.
Exemplul 2: numere cu cifre distincte
Se generează, în ordine crescătoare, numerele de 3 cifre distincte formate cu cifre din mulțimea {1, 3, 5, 7}: 135, 137, 153, 157, 173, … Care este numărul generat după 375?
Aceasta este o generare de aranjamente. Ultima cifră, 5, nu poate deveni 7, pentru că 7 e deja folosit. Cifra din mijloc, 7, nu poate crește. Prima cifră, 3, devine 5, iar restul se completează cu cele mai mici cifre disponibile: 1 și 3. Răspuns: 513.
Tehnica numărării pe prefixe
Când ți se cere a k-a soluție (de exemplu „a opta”), nu le scrii pe toate. Numeri câte soluții încep cu un anumit prefix și sari peste grupuri întregi.
Exemplul 3: a opta combinare
Se generează submulțimile cu 3 elemente ale mulțimii {1, 2, 3, 4, 5, 6}, cu elementele în ordine crescătoare: 123, 124, 125, … Care este a opta soluție?
- Soluțiile care încep cu
1 2: al treilea element poate fi 3, 4, 5 sau 6 → 4 soluții (pozițiile 1–4). - Soluțiile care încep cu
1 3: al treilea element 4, 5 sau 6 → 3 soluții (pozițiile 5–7). - Soluțiile care încep cu
1 4: 5 sau 6 → prima dintre ele este a 8-a.
Răspuns: 1 4 5.
Exemplul 4: poziția unei soluții
Întrebarea inversă: a câta permutare a mulțimii {1, 2, 3, 4} este 3 1 2 4? Permutările care încep cu 1 sunt 3! = 6, cele care încep cu 2 sunt tot 6, deci primele 12 soluții încep cu 1 sau 2. 3 1 2 4 este cea mai mică permutare care începe cu 3, deci este a 13-a.
Exemplul 5: un enunț cu obiecte
Un enunț tipic: „Utilizând metoda backtracking, se generează toate buchetele formate din câte 3 flori distincte din mulțimea {lalea, trandafir, crin, mac, frezie}. Primele trei soluții generate sunt: (lalea, trandafir, crin), (lalea, trandafir, mac), (lalea, trandafir, frezie). Care este a cincea soluție?”
Numerotezi: lalea = 1, trandafir = 2, crin = 3, mac = 4, frezie = 5. Exemplele devin 123, 124, 125, adică ordinea nu contează, iar soluțiile sunt combinări de 5 luate câte 3. Continuarea este 134, apoi 135, adică (lalea, crin, frezie). Dacă ai fi ordonat florile alfabetic, ai fi obținut un răspuns greșit: ordinea vine din enunț, nu din alfabet.
Soluția anterioară
Uneori ți se cere soluția generată înainte de una dată. Aplici aceeași idee în oglindă: cauți cea mai din dreapta poziție care poate fi micșorată la o valoare validă, iar pozițiile din dreapta ei primesc cele mai mari valori valide. De exemplu, la combinările de 5 luate câte 3, înainte de 145 vine 135: poziția a doua scade de la 4 la 3, iar ultima ia valoarea maximă, 5. Verificare: lista este 123, 124, 125, 134, 135, 145, deci răspunsul e corect.
Itemii cu „câte soluții”
Dacă întrebarea este câte soluții sunt în total sau câte au o proprietate, folosește formulele: n! pentru permutări, n!/(n−p)! pentru aranjamente, n!/(p!(n−p)!) pentru combinări. Pentru o proprietate simplă (de exemplu „câte permutări ale lui {1,…,5} încep cu 5”), fixezi ce e impus și numeri ce rămâne liber: aici 4! = 24.
Greșeli care costă puncte
- Ignori condiția suplimentară din enunț (cifre distincte, sumă pară, elemente nevecine) când completezi pozițiile din dreapta.
- Confunzi combinările cu aranjamentele: la combinări, după 1 2 nu vine niciodată 2 1.
- Numeri greșit pozițiile: dacă enunțul îți dă primele trei soluții, a cincea este la două soluții după ultima dată, nu la cinci.
De reținut
- ● Numerotează elementele în ordinea din enunț și identifică tipul de generare din primele soluții date.
- ● Soluția următoare: crești cea mai din dreapta poziție care poate crește, apoi completezi cu cele mai mici valori valide.
- ● Soluția anterioară: micșorezi cea mai din dreapta poziție posibilă și completezi cu cele mai mari valori valide.
- ● Pentru a k-a soluție, numeri soluțiile pe prefixe (de exemplu, (n−1)! permutări încep cu fiecare valoare).
- ● Verifică mereu răspunsul: nu trebuie să existe nicio soluție validă între cea dată și cea găsită.
