Backtracking: toate submulțimile
La o pizzerie poți alege orice combinație de toppinguri: niciunul, unul, două sau toate. Câte variante sunt și cum le generezi pe toate, sistematic? Răspunsul este backtracking: construiești soluția pas cu pas, iar când te întorci dintr-o ramură anulezi ultima alegere (append la intrare, pop la ieșire).
Câte submulțimi are o listă?
Pentru fiecare element ai două opțiuni: îl iei sau nu-l iei. Cu n elemente ai 2 · 2 · ... · 2 = 2ⁿ submulțimi. Pentru [1, 2, 3] sunt 8, inclusiv submulțimea goală și lista întreagă.
Scrie funcția submultimi(lista) care returnează toate submulțimile, în ordinea generării prin backtracking „de la start încolo”: salvezi submulțimea curentă, apoi încerci fiecare element de la start la final. Fără itertools.
- Într-o funcție internă backtrack(start): rezultat.append(curenta[:]).
- Pentru i de la start: append, backtrack(i + 1), pop().
- Trebuie să apară: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]], [[]], 32.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan