Chương trình C++ sinh tất cả tổ hợp của tập ký tự

Chương trình sinh tất cả các tổ hợp (combinations) có thể có từ một tập ký tự cho trước, với độ dài từ 1 đến n.

Thuật toán

Hàm Combi(a[], reqLen, start, currLen, check[], len):
  Nếu currLen > reqLen: return.
  Nếu currLen == reqLen: in các phần tử có check[i] = true.
  Nếu start == len: return.
  check[start] = true;  Combi(..., start+1, currLen+1, ...); // chọn
  check[start] = false; Combi(..., start+1, currLen, ...);   // không chọn

Ví dụ mã nguồn

#include <iostream>
using namespace std;

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

int main() {
    int n;
    cout << "So phan tu: "; cin >> n;
    char a[n];
    bool check[n] = {false};
    for (int i = 0; i < n; i++) {
        cout << "Phan tu " << i+1 << ": "; cin >> a[i];
    }
    for (int len = 1; len <= n; len++) {
        cout << "\nTat ca to hop do dai " << len << ":\n";
        Combi(a, len, 0, 0, check, n);
    }
    return 0;
}

Đầu ra mẫu

So phan tu: 5
Phan tu 1: a
Phan tu 2: b
Phan tu 3: c
Phan tu 4: d
Phan tu 5: e

Tat ca to hop do dai 1:
a b c d e
Tat ca to hop do dai 2:
a b a c a d a e b c b d b e c d c e d e
Tat ca to hop do dai 3:
a b c a b d a b e a c d a c e a d e b c d b c e b d e c d e
Tat ca to hop do dai 4:
a b c d a b c e a b d e a c d e b c d e
Tat ca to hop do dai 5:
a b c d e