Subset Generation

Power set dari sebuah himpunan S adalah kumpulan semua himpunan bagian (subset) dari S, termasuk himpunan kosong dan S sendiri. Bila |S| = n, maka power set berisi tepat 2^n anggota. Banyaknya subset ini tumbuh eksponensial terhadap n: untuk n=20 saja sudah ada lebih dari satu juta subset, dan untuk n=30 lebih dari satu miliar. Pada Chapter ini kita akan membangkitkan power set dengan dua pendekatan klasik — enumerasi bitmask iteratif dan rekursi include/exclude — lalu mengukur ledakan memori yang muncul saat n cukup besar.

Aturan: Definisi Power Set #

Untuk himpunan S = {1, 2, 3} dengan n = 3, power set-nya adalah:

{}           ∅          (subset kosong)
{1}          subset 1 elemen
{2}
{3}
{1,2}        subset 2 elemen
{1,3}
{2,3}
{1,2,3}      subset 3 elemen (S sendiri)

Total 2^3 = 8 subset. Setiap elemen dari S memiliki dua pilihan: masuk ke subset atau tidak. Karena pilihan tiap elemen saling bebas, total kombinasi = 2 × 2 × ... × 2 (n kali) = 2^n.

Pendekatan 1: Enumerasi Bitmask #

Aturan #

Setiap subset dapat direpresentasikan sebagai bitmask n-bit. Bit ke-i bernilai 1 bila elemen a[i] masuk ke subset, dan 0 bila tidak. Dengan demikian, semua subset berkorespondensi satu-satu dengan bilangan bulat 0 hingga 2^n - 1. Kita iterasi seluruh nilai bitmask dan, untuk setiap bitmask, cetak elemen a[i] yang bit-nya 1.

Mekanisme Kerja #

Iterasi bitmask dari 0 (subset kosong) sampai (1<<n) - 1 (subset lengkap). Untuk setiap bitmask mask, kita cek bit ke-i dengan ekspresi mask & (1 << i). Bila hasilnya bukan nol, elemen a[i] disertakan. Karena iterasi dilakukan secara numerik naik dari 0, urutan subset yang dibangkitkan mengikuti pola Gray-code-like: subset dengan elemen lebih sedikit muncul lebih awal.

Kode: Enumerasi Bitmask #

#include <iostream>
#include <vector>

void cetak_subset(const std::vector<int>& a, int mask) {
    std::cout << '{';
    bool first = true;
    for (size_t i = 0; i < a.size(); ++i) {
        if (mask & (1 << i)) {
            if (!first) std::cout << ',';
            std::cout << a[i];
            first = false;
        }
    }
    std::cout << "}\n";
}

int main() {
    std::vector<int> a = {1, 2, 3};
    int n = static_cast<int>(a.size());
    int total = 1 << n;                       // 2^n
    std::cout << "power set dengan bitmask (n=" << n << "):\n";
    for (int mask = 0; mask < total; ++mask) {
        cetak_subset(a, mask);
    }
    std::cout << "total subset: " << total << '\n';
    return 0;
}

Output yang Dihasilkan:

power set dengan bitmask (n=3):
{}
{1}
{2}
{1,2}
{3}
{1,3}
{2,3}
{1,2,3}
total subset: 8

Mari kita telaah apa yang terjadi pada baris-baris kode di atas:

1. Baris int total = 1 << n;: menghitung 2^n dengan operator shift-left. Untuk n=3, hasilnya 8. Ekspresi ini setara dengan pow(2, n) tetapi jauh lebih cepat dan tetap presisi untuk n ≤ 30 (di atas itu, gunakan 1LL << n untuk menghindari overflow int).
2. Loop for (int mask = 0; mask < total; ++mask): iterasi semua bitmask dari 0 hingga 2^n - 1. Iterasi ke-0 selalu menghasilkan subset kosong karena tidak ada bit yang menyala.
3. Baris mask & (1 << i): tes bit ke-i dari mask. Hasilnya bukan nol bila bit tersebut menyala. Operator & (bitwise AND) dengan 1 << i mengisolasi bit tunggal pada posisi i.
4. Variabel first: mengontrol pencetakan koma pemisah. Setelah elemen pertama dicetak, first menjadi false, sehingga elemen berikutnya didahului tanda koma.
5. Urutan output: pola {}, {1}, {2}, {1,2}, {3}, {1,3}, ... adalah konsekuensi langsung dari iterasi numerik mask naik. Untuk mask=0 tidak ada elemen; mask=1 (binary 001) hanya elemen a[0]; mask=2 (binary 010) hanya a[1]; mask=3 (binary 011) elemen a[0] dan a[1]; dan seterusnya.

Pendekatan 2: Rekursi Include/Exclude #

Aturan #

Rekursi memproses elemen satu per satu dari indeks 0 hingga n-1. Pada setiap elemen, kita bercabang dua: exclude (lewati elemen ini) dan include (masukkan ke cur, lalu lanjut). Saat i == n, semua elemen sudah dipertimbangkan — cur berisi satu subset final.

Mekanisme Kerja #

State rekursi terdiri dari indeks i (elemen berikutnya yang diproses) dan vektor cur (akumulator subset parsial). Pemanggilan rekursif pertama (exclude) dilakukan sebelum push, jadi subset kosong muncul paling awal di cabang paling dalam. Setelah pemanggilan kedua (include), kita pop_back() untuk memulihkan cur agar cabang saudara mulai dari state bersih. Pola ini identik dengan kombinasi pada Chapter sebelumnya — bedanya, di sini kita mencatat subset pada setiap kedalaman, tidak hanya saat terkumpul k elemen.

Kode: Rekursi Include/Exclude #

#include <iostream>
#include <vector>

void subset_rekursif(const std::vector<int>& a, size_t i,
                     std::vector<int>& cur,
                     std::vector<std::vector<int>>& hasil)
{
    if (i == a.size()) {
        hasil.push_back(cur);                 // catat subset final
        return;
    }
    // Cabang 1: exclude a[i]
    subset_rekursif(a, i + 1, cur, hasil);
    // Cabang 2: include a[i]
    cur.push_back(a[i]);
    subset_rekursif(a, i + 1, cur, hasil);
    cur.pop_back();
}

int main() {
    std::vector<int> a = {1, 2, 3};
    std::vector<int> cur;
    std::vector<std::vector<int>> hasil;
    subset_rekursif(a, 0, cur, hasil);
    std::cout << "power set dengan rekursi (n=" << a.size() << "):\n";
    for (const auto& s : hasil) {
        std::cout << '{';
        for (size_t k = 0; k < s.size(); ++k) {
            if (k) std::cout << ',';
            std::cout << s[k];
        }
        std::cout << "}\n";
    }
    std::cout << "total subset: " << hasil.size() << '\n';
    return 0;
}

Output yang Dihasilkan:

power set dengan rekursi (n=3):
{}
{3}
{2}
{2,3}
{1}
{1,3}
{1,2}
{1,2,3}
total subset: 8

Mari kita telaah apa yang terjadi pada baris-baris kode di atas:

1. Parameter i: indeks elemen yang sedang dipertimbangkan. Dimulai dari 0 di panggilan akar, dinaikkan ke i + 1 di kedua cabang rekursi.
2. Base case i == a.size(): semua elemen sudah diproses. cur berisi subset lengkap; salin ke hasil. Karena cur di-pass by reference, kita harus salin (bukan referensi) — hasil.push_back(cur) melakukan copy otomatis.
3. Cabang exclude dipanggil lebih dulu: ini menentukan urutan output. Karena exclude untuk a[0] dilakukan sebelum include, subset tanpa a[0] muncul lebih dulu.
4. Baris cur.push_back(a[i]) (include): tambahkan a[i] ke subset parsial. Kedalaman rekursi berikutnya akan melihat cur dengan satu elemen ekstra.
5. Baris cur.pop_back() (unchoose): pulihkan cur ke kondisi sebelum include. Tanpa baris ini, state bocor ke cabang lain yang seharusnya exclude — subset akan terakumulasi elemen yang tidak diinginkan.
6. Urutan output berbeda dengan bitmask: rekursi menghasilkan {}, {3}, {2}, {2,3}, {1}, {1,3}, {1,2}, {1,2,3} — subset dikelompokkan berdasarkan cabang include/exclude, bukan berdasarkan bitmask numerik. Total tetap 8.

Perbandingan Bitmask vs Rekursi #

Kedua pendekatan menghasilkan 2^n subset. Pilihan tergantung kebutuhan: bila kita hanya ingin mencetak atau memproses tiap subset sekali, bitmask lebih ringkas; bila kita butuh pruning (misalnya subset sum ≤ target), rekursi lebih natural.

Pertimbangan Memori: Ledakan 2^n #

Walaupun membangkitkan semua subset secara konseptual sederhana, menyimpan semua subset dalam vector<vector<int>> menjadi tidak realistis untuk n moderat. Setiap subset rata-rata berisi n/2 elemen, masing-masing int 4 byte, ditambah overhead vektor (size, capacity, pointer ≈ 24 byte per vekktor).

Kode: Estimasi Memori Power Set #

#include <iostream>
#include <vector>

int main() {
    std::cout << "n  | 2^n        | estimasi memori vector<vector<int>>\n";
    std::cout << "---|------------|------------------------------------\n";
    for (int n : {10, 20, 25, 30}) {
        long long total = 1LL << n;                 // 2^n
        // avg n/2 elemen per subset, 4 byte per int, +24 byte overhead vektor
        double bytes = static_cast<double>(total) * (n / 2.0 * 4.0 + 24.0);
        double mb = bytes / (1024.0 * 1024.0);
        std::cout << n << "  | " << total;
        if (total < 1000000) std::cout << "       | ";
        else if (total < 1000000000) std::cout << "    | ";
        else std::cout << "   | ";
        std::cout << mb << " MB\n";
    }
    return 0;
}

Output yang Dihasilkan:

n  | 2^n        | estimasi memori vector<vector<int>>
---|------------|------------------------------------
10  | 1024       | 0.0429688 MB
20  | 1048576    | 64 MB
25  | 33554432    | 2368 MB
30  | 1073741824   | 86016 MB

Mari kita telaah apa yang terjadi pada baris-baris kode di atas:

1. Baris long long total = 1LL << n;: untuk n = 30, hasil 2^30 ≈ 1.07 miliar sudah melampaui kapasitas int 32-bit bertanda (INT_MAX ≈ 2.1 miliar). Penggunaan 1LL (literal long long) mencegah overflow.
2. Estimasi n/2 * 4 + 24: rata-rata subset berisi n/2 elemen int (4 byte tiap), ditambah overhead vektor (~24 byte untuk pointer, size, capacity). Nilai ini konservatif; vektor int kosong sebenarnya tidak mengalokasikan apa-apa, jadi subtotal subset kosong lebih kecil.
3. n=25 ≈ 2.4 GB: sudah melampaui batas memori proses 32-bit umum. Banyak sistem operasi akan menolak alokasi atau membunuh proses (OOM killer).
4. n=30 ≈ 86 GB: jauh melampaui RAM workstation biasa. Ini mengonfirmasi bahwa menyimpan seluruh power set untuk n ≥ 25 tidak praktis.

Pola Streaming dengan Bitmask #

Bila tujuan akhir adalah menghitung jumlah subset yang memenuhi kriteria (misalnya subset dengan jumlah elemen genap), kita tidak perlu menyimpan subset sama sekali. Cukup hitung langsung dari bitmask:

Kode: Streaming Hitung Subset Dengan Jumlah Genap #

#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {1, 2, 3, 4};
    int n = static_cast<int>(a.size());
    int total = 1 << n;
    int hitung_genap = 0;
    for (int mask = 0; mask < total; ++mask) {
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) ++cnt;
        }
        if (cnt % 2 == 0) ++hitung_genap;
    }
    std::cout << "n=" << n << ", 2^n=" << total
              << ", subset dengan jumlah elemen genap: "
              << hitung_genap << '\n';
    return 0;
}

Output yang Dihasilkan:

n=4, 2^n=16, subset dengan jumlah elemen genap: 8

1. Tanpa penyimpanan: variabel lokal cnt dan hitung_genap hanya butuh beberapa byte, tidak peduli berapa n. Pola streaming ini menskalakan hingga n ≈ 30 dalam waktu detik.
2. Hasil 8 dari 16: tepat setengah subset berukuran genap. Ini bukan kebetulan — secara kombinatorial, jumlah subset berukuran genap = jumlah subset berukuran ganjil = 2^(n-1) untuk n ≥ 1. Buktinya: pasangkan tiap subset dengan subset yang diperoleh dengan menambah/menghapus elemen a[0]; pasangan ini selalu terdiri dari satu genap dan satu ganjil.

Ringkasan #

• Power set dari S dengan |S| = n memiliki 2^n anggota, termasuk himpunan kosong dan S sendiri.
• Enumerasi bitmask: iterasi mask dari 0 hingga 2^n - 1, dan sertakan a[i] bila bit ke-i menyala. Sederhana, iteratif, dan hemat memori.
• Rekursi include/exclude: bercabang exclude lalu include untuk setiap elemen. Lebih natural saat dibutuhkan pruning (misalnya subset sum, subset terbatas).
• Urutan output berbeda: bitmask mengikuti urutan numerik; rekursi mengikuti DFS cabang.
• Memori meledak cepat: untuk n=25, vector<vector<int>> sudah memakan ~1.4 GB; n=30 ~48 GB.
• Untuk n ≥ 25, gunakan pola streaming: proses tiap subset segera tanpa akumulasi.