Chương trình C++ sinh tất cả tập con của tập cho trước theo thứ tự từ điển

Đây là chương trình C++ sinh tất cả tập con của một tập cho trước theo thứ tự từ điển (lexicographic order). Thuật toán in tất cả tổ hợp có thể có của mỗi độ dài từ mảng cho trước theo thứ tự tăng dần. Độ phức tạp thời gian O(n * 2^n).

Thuật toán

Bắt đầu
  Với mỗi độ dài 'i' gọi hàm GenAllSubset():
    1) Trong GenAllSubset(), nếu currLen > reqLen thì trả về.
    2) Ngược lại, nếu currLen == reqLen thì có dãy mới sinh ra, in ra.
    3) Nếu tiếp tục với start = 'true' và gọi đệ quy GenAllSubset() với currLen+1 và s+1.
       ngược lại
         tiếp tục với start = 'false' và gọi đệ quy GenAllSubset() với s+1.
Kết thúc

Ví dụ mã nguồn

#include <iostream>
using namespace std;

void Sorting(int a[], int n) { // sắp xếp mảng
    int i, j, t;
    for (i = 0; i < n; i++) {
        for (j = i+1; j < n; j++) {
            if (a[i] > a[j]) {
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

void GenAllSubset(int a[], int reqLen, int s, int currLen, bool check[], int len) {
    if (currLen > reqLen)
        return;
    else if (currLen == reqLen) {
        cout << "\t";
        cout << "{ ";
        for (int i = 0; i < len; i++) {
            if (check[i] == true) {
                cout << a[i] << " ";
            }
        }
        cout << "}\n";
        return;
    }
    if (s == len)
        return;
    check[s] = true;
    GenAllSubset(a, reqLen, s + 1, currLen + 1, check, len);
    check[s] = false;
    GenAllSubset(a, reqLen, s + 1, currLen, check, len);
}

int main() {
    int i, n;
    bool ch[n];
    cout << "Nhập số phần tử mảng: ";
    cin >> n;
    int arr[n];
    cout << "\n";
    for (i = 0; i < n; i++) {
        cout << "Nhập phần tử " << i+1 << ": ";
        cin >> arr[i];
        ch[i] = false;
    }
    Sorting(arr, n);
    cout << "\nTất cả tập con của tập cho trước theo thứ tự từ điển: \n";
    cout << "\t{ }\n";
    for (i = 1; i <= n; i++) {
        GenAllSubset(arr, i, 0, 0, ch, n);
    }
    return 0;
}

Kết quả

Nhập số phần tử mảng: 6
Nhập phần tử 1: 3
Nhập phần tử 2: 2
Nhập phần tử 3: 1
Nhập phần tử 4: 7
Nhập phần tử 5: 6
Nhập phần tử 6: 5

Tất cả tập con của tập cho trước theo thứ tự từ điển:
{ }
{ 1 }
{ 2 }
{ 3 }
{ 5 }
{ 6 }
{ 7 }
{ 1 2 }
{ 1 3 }
{ 1 5 }
{ 1 6 }
{ 1 7 }
{ 2 3 }
{ 2 5 }
{ 2 6 }
{ 2 7 }
{ 3 5 }
{ 3 6 }
{ 3 7 }
{ 5 6 }
{ 5 7 }
{ 6 7 }
{ 1 2 3 }
{ 1 2 5 }
{ 1 2 6 }
{ 1 2 7 }
{ 1 3 5 }
{ 1 3 6 }
{ 1 3 7 }
{ 1 5 6 }
{ 1 5 7 }
{ 1 6 7 }
{ 2 3 5 }
{ 2 3 6 }
{ 2 3 7 }
{ 2 5 6 }
{ 2 5 7 }
{ 2 6 7 }
{ 3 5 6 }
{ 3 5 7 }
{ 3 6 7 }
{ 5 6 7 }
{ 1 2 3 5 }
{ 1 2 3 6 }
{ 1 2 3 7 }
{ 1 2 5 6 }
{ 1 2 5 7 }
{ 1 2 6 7 }
{ 1 3 5 6 }
{ 1 3 5 7 }
{ 1 3 6 7 }
{ 1 5 6 7 }
{ 2 3 5 6 }
{ 2 3 5 7 }
{ 2 3 6 7 }
{ 2 5 6 7 }
{ 3 5 6 7 }
{ 1 2 3 5 6 }
{ 1 2 3 5 7 }
{ 1 2 3 6 7 }
{ 1 2 5 6 7 }
{ 1 3 5 6 7 }
{ 2 3 5 6 7 }
{ 1 2 3 5 6 7 }