Backtracking fără drum.pop(): drumul se lungește și lipsesc soluții
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
for i in range(start, len(elemente)):
drum.append(elemente[i])
merg(i + 1)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ă
for x in optiuni:
drum.append(x)
if valid(drum):
merg()
drum.pop()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ă
drum.append(x)
if len(drum) == k:
rezultat.append(drum[:])
return
merg(i + 1)
drum.pop()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ă 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.
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)['A', 'B'] ['A', 'C'] ['B', 'C']
Indiciu
După apelul recursiv merg(i + 1), scoate ultimul element ales cu drum.pop().
Reparația
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)
drum.pop()
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)De ce merge
Fără pop(), după echipa ['A', 'B'] codul adăuga C peste ea și obținea ['A', 'B', 'C'], care nu mai are lungimea 2, apoi drumul creștea mereu. Cu drum.pop() după apelul recursiv, fiecare alegere se anulează înainte de următoarea, iar drumul revine la starea de dinainte. Așa A se combină pe rând cu B și cu C, apoi B cu C.
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
Backtracking-ul returnează liste goale: [[], [], []] Ai adăugat în rezultat chiar lista de lucru (rezultat.append(drum)), nu o copie a ei. La final backtracking-ul golește lista, deci toate intrările arată goale. Adaugă o copie: rezultat.append(drum[:]) sau list(drum). Permutările ies duplicate când lista are elemente care se repetă Backtracking-ul tratează cele două litere A din „AAB” ca elemente diferite, deci fiecare ordine apare de mai multe ori. Sortează elementele și sari peste un element egal cu cel dinaintea lui la același nivel: if i > 0 and ramase[i] == ramase[i - 1]: continue. Argumentul implicit mutabil (rezultat=[]) păstrează valorile între apeluri Valoarea implicită a unui parametru (rezultat=[], memo={}) se creează o singură dată, când e definită funcția, și e aceeași listă la toate apelurile, așa că al doilea apel vede ce a adăugat primul. Folosește rezultat=None și creează lista în funcție: if rezultat is None: rezultat = []. Î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.
