Chương trình C++ sinh tất cả cặp tập con hợp thành tập gốc

Chương trình liệt kê tất cả các cặp tập con (A, B) sao cho A ∪ B = tập gốc S. Số cặp như vậy là 2^(n-1) với n là số phần tử.

Thuật toán

Hàm UnionSet(a[], n):
  Sinh mã nhị phân từ 0 đến 2^(n-1)-1.
  Với mỗi mã:
    Tập 1: các phần tử a[i] nơi mã[i] = '1'.
    Tập 2: các phần tử a[i] nơi mã[i] = '0'.
  In hai tập theo cặp.

Ví dụ mã nguồn

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

void display(char code[], int a[], int n) {
    cout << "\t{ ";
    for (int i = 0; i < n; i++)
        if (code[i] == '1') cout << a[i] << " ";
    cout << "} { ";
    for (int i = 0; i < n; i++)
        if (code[i] == '0') cout << a[i] << " ";
    cout << "}\n";
}

void UnionSet(int a[], int n) {
    char binary[20] = {0};
    int r = pow(2, n-1);
    for (int i = 0; i < n; i++) binary[i] = '0';
    for (int i = 0; i < r; i++) {
        display(binary, a, n);
        int l = n-1;
        while (true) {
            if (binary[l] == '0') { binary[l] = '1'; break; }
            else { binary[l] = '0'; l--; }
        }
    }
}

int main() {
    int n;
    cout << "So phan tu: "; cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cout << "Phan tu " << i+1 << ": "; cin >> a[i];
    }
    cout << "Cac cap tap con hop thanh tap goc:\n";
    UnionSet(a, n);
    return 0;
}

Đầu ra mẫu

So phan tu: 4
Phan tu 1: 4
Phan tu 2: 3
Phan tu 3: 2
Phan tu 4: 1
Cac cap tap con hop thanh tap goc:
{ } { 4 3 2 1 }
{ 1 } { 4 3 2 }
{ 2 } { 4 3 1 }
{ 2 1 } { 4 3 }
{ 3 } { 4 2 1 }
{ 3 1 } { 4 2 }
{ 3 2 } { 4 1 }
{ 3 2 1 } { 4 }