Submulțimi — AlgoClar

De ce contează?

Faci bagajul și ai n obiecte; pentru fiecare decizi „îl iau / nu îl iau". Toate variantele posibile de bagaj sunt toate submulțimile celor n obiecte. De la a nu lua nimic până la a le lua pe toate — sunt 2ⁿ moduri, și le putem genera sistematic.

Câte submulțimi și de ce 2ⁿ

Pentru o mulțime cu n elemente, fiecare element are două stări: în submulțime sau nu. Decizii independente → 2 · 2 · ... · 2 = 2ⁿ submulțimi (inclusiv mulțimea vidă).

Pentru : ∅, , , , , , , — exact 2³ = 8.

Varianta 1: backtracking („iau / nu iau")

La fiecare element ramifici în două: îl incluzi sau nu.

#include <iostream>
using namespace std;

int n;
bool inclus[20];

void genereaza(int pas) {
    if (pas == n) {                 // submultime completa
        cout << "{ ";
        for (int i = 0; i < n; i++) if (inclus[i]) cout << i << " ";
        cout << "}\n";
        return;
    }
    inclus[pas] = false;            // nu iau elementul pas
    genereaza(pas + 1);
    inclus[pas] = true;             // iau elementul pas
    genereaza(pas + 1);
}

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

Observația-cheie

Cele două apeluri recursive — unul cu inclus[pas] = false, altul cu true — explorează ambele ramuri pentru fiecare element. Arborele de decizie are 2ⁿ frunze, câte una per submulțime.

Varianta 2: măști de biți

O submulțime ↔ un număr de la 0 la 2ⁿ−1. Bitul k aprins = elementul k e inclus:

for (int masca = 0; masca < (1 << n); masca++) {    // 2^n submultimi
    cout << "{ ";
    for (int k = 0; k < n; k++) {
        if (masca & (1 << k)) cout << k << " ";     // bitul k e 1?
    }
    cout << "}\n";
}

Observația-cheie

Varianta cu măști e mai scurtă și fără recursie — parcurgi toate numerele de la 0 la 2ⁿ−1. Leagă direct de [[punte-masti-biti]]: fiecare submulțime e un întreg, iar testul de apartenență e masca & (1 << k).

Complexitate

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

2ⁿ submulțimi, fiecare afișată în O(n). Fezabil pentru n ≤ ~20.

Vizualizare

Urmărește arborele de decizie: la fiecare element se ramifică în „iau / nu iau”, iar frunzele sunt submulțimile:

Indiciu

Observă cum fiecare nivel al arborelui corespunde unui element, iar coborârea pe o ramură adaugă (sau nu) elementul. O frunză = o submulțime completă.

Greșeli frecvente

Capcane reale la generarea submulțimilor:

Uiți cazul de bază: recursia nu se oprește la pas == n.
Procesezi submulțimea înainte de a fi completă: afișezi la fiecare pas, nu doar la frunze.
Shift cu overflow la măști: 1 << n pentru n ≥ 31 se sparge în int. Folosește 1LL << n la n mare.
Generezi pentru n mare: 2ⁿ explodează (2³⁰ ≈ un miliard). Verifică limita lui n.

De reținut

O mulțime cu n elemente are 2ⁿ submulțimi (fiecare element: iau / nu iau).
Generezi prin backtracking (ramifici în două per element) sau prin măști de biți (0..2ⁿ−1).
O(2ⁿ · n); fezabil pentru n ≤ ~20; 1LL << n la n mare.