De ce contează?
Ești la un restaurant și meniul are trei feluri: supă, friptură, desert. Pentru fiecare fel iei o singură decizie, separat de celelalte: îl iau sau nu îl iau. Poți comanda nimic, doar supa, supă și desert, sau tot. Fiecare comandă posibilă este o submulțime a meniului — iar a le enumera pe toate înseamnă exact a parcurge fiecare combinație de „iau / nu iau", fel cu fel.
Intuiția
O submulțime se construiește răspunzând, element cu element, la o singură
întrebare: „îl pun înăuntru sau nu?". Cum fiecare element are exact 2 răspunsuri
independente, o mulțime cu n elemente are 2 x 2 x ... x 2 = 2^n submulțimi.
Ca să le generezi pe toate, parcurgi sistematic toate combinațiile de decizii.
Cele 2 alegeri per element îți dau două căi de a enumera totul, echivalente:
un backtracking cu două ramuri pe fiecare nivel (ramura „iau" și ramura „nu
iau"), sau o mască binară — un număr de la 0 la 2^n - 1 în care bitul k
spune dacă elementul k e luat. Aceeași 2^n combinații, două ambalaje.