Submulțimi — fiecare element intră sau nu

De ce contează?

Îți faci bagajul pentru o excursie. Pentru fiecare obiect de pe listă iei o singură decizie: îl pun în rucsac sau nu. Toate combinațiile posibile de „da/nu" sunt exact submulțimile listei tale de obiecte.

Ce este o submulțime

O submulțime a unei mulțimi se obține alegând o parte dintre elemente (eventual niciunul sau pe toate). O mulțime cu n elemente are exact 2ⁿ submulțimi: fiecare element are două variante independente — prezent sau absent.

Observația-cheie

Două elemente → 4 submulțimi, trei → 8, zece → 1024. Numărul crește exponențial, deci generarea tuturor submulțimilor are sens doar pentru n mic (în practică n ≤ 20-25).

Două moduri de a le genera

Cu mască binară: fiecare submulțime ↔ un număr de la 0 la 2ⁿ-1. Bitul i spune dacă elementul i e prezent.

bit	1	0	1	1
elem	a	b	c	d

Masca 1011 → submulțimea {a, c, d}: bit 1 înseamnă element prezent.

Cu backtracking: pentru fiecare element ramifici recursiv — o cale îl include, una îl exclude. Mai natural când vrei să te oprești devreme sub o condiție.

Implementare C++ (backtracking)

#include <iostream>
using namespace std;

int n = 3;
bool inSubmultime[20];

void genereaza(int i) {
    if (i == n) {                 // am decis pentru toate elementele
        cout << "{ ";
        for (int j = 0; j < n; j++) {
            if (inSubmultime[j]) cout << j + 1 << " ";
        }
        cout << "}\n";
        return;
    }
    inSubmultime[i] = true;       // ramura: includem elementul i
    genereaza(i + 1);
    inSubmultime[i] = false;      // ramura: il excludem
    genereaza(i + 1);
}

int main() {
    genereaza(0);                 // 8 submultimi pentru n=3
    return 0;
}

Implementare C++ (mască binară)

for (int mask = 0; mask < (1 << n); mask++) {  // 1<<n inseamna 2^n
    cout << "{ ";
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i)) cout << i + 1 << " ";  // bitul i este 1?
    }
    cout << "}\n";
}

Complexitate

Operație	Timp	Spațiu
Generarea tuturor submulțimilor	O(2ⁿ · n)	O(n)

2ⁿ submulțimi, fiecare afișată în O(n). Pentru n mare e imposibil — exponențial.

Vizualizare

Urmărește arborele de decizii: la fiecare nivel, o ramură include elementul, cealaltă îl exclude. Frunzele sunt cele 2ⁿ submulțimi:

Greșeli frecvente

Capcane frecvente:

1 << n depășește int pentru n ≥ 31. Folosește 1LL << n (long long) la măști mari.
Uiți să anulezi decizia (inSubmultime[i] = false). Fără pasul de „undo", ramurile se contaminează între ele.
Confunzi numărul de submulțimi cu 2·n. Sunt 2ⁿ, nu 2n — crește exponențial.
Generezi submulțimi pentru n mare. La n = 40 sunt peste 10¹² submulțimi — depășești timpul. Caută altă abordare (formulă, programare dinamică).

Recapitulare

O mulțime cu n elemente are 2ⁿ submulțimi (fiecare element: prezent sau absent).
Backtracking = ramifici include/exclude la fiecare element; masca binară = un bit per element.
Generarea e exponențială, deci fezabilă doar pentru n mic.