Chương trình C++ sinh tất cả tổ hợp từ danh sách số

Chương trình sinh tất cả các tổ hợp (combinations) của một danh sách số cho trước, với độ dài từ 1 đến n. Sử dụng kỹ thuật backtracking với mảng boolean đánh dấu.

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ử check[i]=true.
  Nếu start == len: return.
  check[start]=true; Combi(..., start+1, currLen+1, ...);
  check[start]=false; Combi(..., start+1, currLen, ...).

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 << "\nTo hop do dai " << len << ":\n";
        Combi(a, len, 0, 0, check, n);
    }
    return 0;
}

Đầu ra mẫu

So phan tu: 4
Phan tu: 4 3 2 1
To hop do dai 1: 4 3 2 1
To hop do dai 2: 4 3, 4 2, 4 1, 3 2, 3 1, 2 1
To hop do dai 3: 4 3 2, 4 3 1, 4 2 1, 3 2 1
To hop do dai 4: 4 3 2 1