...
Eroare Algoritmi și structuri de date · Recursivitate și backtracking

Backtracking fără drum.pop(): drumul se lungește și lipsesc soluții

Pe scurt

Ai adăugat elementul în drum înainte de apelul recursiv, dar nu l-ai scos după. Drumul crește la fiecare ramură și nu mai are lungimea cerută. Pune drum.pop() imediat după apelul recursiv, ca să anulezi alegerea înainte de următoarea.

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

Backtracking-ul are trei pași care merg mereu împreună: alegi (drum.append(x)), explorezi (apelul recursiv) și anulezi alegerea (drum.pop()). Dacă lipsește ultimul pas, elementul ales rămâne în listă și când încerci ramura următoare. Lista drum e una singură, partajată de toate apelurile, deci se lungește continuu.

Python nu dă nicio eroare. Simptomele sunt: lipsesc soluții (condiția len(drum) == k nu mai e adevărată după prima ramură), apar soluții cu prea multe elemente sau rezultatul are o singură combinație.

Ca să găsești locul, afișează drum la intrarea în funcție: dacă vezi liste din ce în ce mai lungi, care nu scad niciodată, lipsește pop(). În „Repară tu”, testul cu assert afișează lista reală de combinații.

De ce apare: cauzele frecvente

1Lipsește drum.pop() după apelul recursiv

Greșit
PYTHON
for i in range(start, len(elemente)):
    drum.append(elemente[i])
    merg(i + 1)
Corect
PYTHON
for i in range(start, len(elemente)):
    drum.append(elemente[i])
    merg(i + 1)
    drum.pop()

Fără pop(), elementul ales rămâne în drum și pentru următoarea iterație. Cu pop(), drumul revine exact la starea dinaintea alegerii.

2pop() pus în ramura greșită

Greșit
PYTHON
for x in optiuni:
    drum.append(x)
    if valid(drum):
        merg()
        drum.pop()
Corect
PYTHON
for x in optiuni:
    drum.append(x)
    if valid(drum):
        merg()
    drum.pop()

Fiecare append are nevoie de un pop, indiferent dacă ai explorat sau nu. Pune pop() la același nivel de indentare ca append().

3Return înainte de pop() în caz de bază

Greșit
PYTHON
drum.append(x)
if len(drum) == k:
    rezultat.append(drum[:])
    return
merg(i + 1)
drum.pop()
Corect
PYTHON
drum.append(x)
if len(drum) == k:
    rezultat.append(drum[:])
else:
    merg(i + 1)
drum.pop()

return iese din funcție înainte de pop(), deci elementul rămâne în drum. Verifică cazul de bază la începutul funcției sau folosește else.

Repară tu

Repară eroarea, direct în pagină

Funcția combinari(elemente, k) trebuie să formeze toate echipele de câte k persoane. Testul cu assert pică: lipsesc echipe, pentru că alegerile nu se anulează. Repar-o ca să afișeze cele trei echipe de câte doi oameni din A, B, C.

Codul care dă eroarea
PYTHON
def combinari(elemente, k):
    rezultat = []
    drum = []
    def merg(start):
        if len(drum) == k:
            rezultat.append(drum[:])
            return
        for i in range(start, len(elemente)):
            drum.append(elemente[i])
            merg(i + 1)
    merg(0)
    return rezultat

rez = combinari(['A', 'B', 'C'], 2)
assert rez == [['A', 'B'], ['A', 'C'], ['B', 'C']], f'echipe gresite: {rez}'
for echipa in rez:
    print(echipa)
După reparație, programul afișează
['A', 'B']
['A', 'C']
['B', 'C']
Indiciu

După apelul recursiv merg(i + 1), scoate ultimul element ales cu drum.pop().

Cum o eviți pe viitor

Scrie append și pop în același timp, unul sub altul, cu apelul recursiv între ele. Dacă vrei să eviți complet problema, trimite o listă nouă la fiecare apel (merg(drum + [x])): e puțin mai lent, dar nu ai nimic de anulat. Testează pe un exemplu mic (3 elemente, k = 2) și compară cu lista scrisă de mână.

Întrebări frecvente

De ce mai am nevoie de drum[:] dacă am pus pop()?

Pentru că rezultat.append(drum) salvează aceeași listă, pe care pop() o golește ulterior. Copia drum[:] îngheață combinația în momentul în care e completă.

Varianta cu drum + [x] e mai bună?

E mai sigură, pentru că fiecare apel are lista lui. Costă o copie la fiecare pas, ceea ce contează doar la căutări foarte mari.

Erori înrudite

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție

Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.