Chương trình C++ sinh tập con có đúng k phần tử

Chương trình liệt kê tất cả các tập con có đúng k phần tử từ một tập cho trước, sử dụng kỹ thuật backtracking với mảng đánh dấu boolean.

Thuật toán

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

Ví dụ mã nguồn

#include <iostream>
using namespace std;

void PossibleSubSet(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;
    PossibleSubSet(a, reqLen, s+1, currLen+1, check, l);
    check[s] = false;
    PossibleSubSet(a, reqLen, s+1, currLen, check, l);
}

int main() {
    int n, m;
    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];
    }
    cout << "Do dai tap con k: "; cin >> m;
    cout << "Cac tap con co " << m << " phan tu:\n";
    PossibleSubSet(a, m, 0, 0, check, n);
    return 0;
}

Đầu ra mẫu

So phan tu: 7
Phan tu 1: 7
Phan tu 2: 6
Phan tu 3: 5
Phan tu 4: 4
Phan tu 5: 3
Phan tu 6: 2
Phan tu 7: 1
Do dai tap con k: 6
Cac tap con co 6 phan tu:
7 6 5 4 3 2
7 6 5 4 3 1
7 6 5 4 2 1
7 6 5 3 2 1
7 6 4 3 2 1
7 5 4 3 2 1
6 5 4 3 2 1