Chương trình C++ sinh tập con bằng phương pháp đếm nhị phân

Sử dụng việc đếm nhị phân từ 0 đến 2^n - 1 để sinh tất cả tập con. Mỗi bit trong số nhị phân đại diện cho việc có/không có phần tử tương ứng.

Thuật toán

Hàm BinaryCounting(a[], n):
  r = 2^n.
  Khởi tạo chuỗi nhị phân n bit toàn 0.
  Với i từ 0 đến r-1:
    In tập con tương ứng với chuỗi nhị phân hiện tại.
    Tăng chuỗi nhị phân lên 1 (dùng goto/while).

Ví dụ mã nguồn

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

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

void BinaryCounting(int a[], int n) {
    int r = pow(2, n);
    char bin[20] = {0};
    for (int i = 0; i < n; i++) bin[i] = '0';
    for (int i = 0; i < r; i++) {
        printSubset(bin, a, n);
        int l = n-1;
        while (true) {
            if (bin[l] == '0') { bin[l] = '1'; break; }
            else { bin[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 tap con (phuong phap dem nhi phan):\n";
    BinaryCounting(a, n);
    return 0;
}

Đầu ra mẫu

So phan tu: 4
Phan tu: 4 3 2 1
Cac tap con:
{ }
{ 1 }
{ 2 }
{ 2 1 }
{ 3 }
{ 3 1 }
{ 3 2 }
{ 3 2 1 }
{ 4 }
{ 4 1 }
{ 4 2 }
{ 4 2 1 }
{ 4 3 }
{ 4 3 1 }
{ 4 3 2 }
{ 4 3 2 1 }