// Contoh Bab 11: menelusuri semua himpunan bagian dengan bilangan biner.
//
// Compile:  g++ -std=c++17 -O2 -o himpunan exercises/11/02-himpunan-bagian.cpp
// Jalankan: ./himpunan
// Contoh masukan: 4
//                 1 2 3 4

#include <iostream>
#include <ctime>
using namespace std;

int a[25];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    clock_t t0 = clock();
    long long total_himpunan = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        long long jumlah = 0;
        if (n <= 4) cout << "{ ";
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {            // bit ke-i menyala
                jumlah += a[i];
                if (n <= 4) cout << a[i] << " ";
            }
        }
        if (n <= 4) cout << "} jumlah = " << jumlah << "\n";
        total_himpunan++;
    }

    cout << "banyak himpunan bagian: " << total_himpunan << "\n";
    cout << "waktu: " << (double)(clock() - t0) / CLOCKS_PER_SEC << " detik\n";

    // Coba ini: jalankan dengan n = 20 (data boleh sembarang).
    return 0;
}