In tất cả tổ hợp r phần tử từ mảng n trong C++

Cho mảng kích thước n và số r. In tất cả tổ hợp chập r của n phần tử (thứ tự không quan trọng).

Ví dụ

arr = {1,2,3,4,5}, r = 3 → {1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}

Phương pháp 1: Đệ quy cố định phần tử (Fixed element + recurse)

Chỉ cố định n-r+1 phần tử đầu, đệ quy phần còn lại.

#include <iostream>
using namespace std;

void printCombination(int arr[], int comb[], int start, int end, int index, int r) {
    if (index == r) {
        cout << "{ ";
        for (int j = 0; j < r; j++) cout << comb[j] << " ";
        cout << "}\t";
        return;
    }
    for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
        comb[index] = arr[i];
        printCombination(arr, comb, i + 1, end, index + 1, r);
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int r = 3, n = 5;
    int comb[r];
    cout << "Combinations:\n";
    printCombination(arr, comb, 0, n - 1, 0, r);
    return 0;
}

Phương pháp 2: Bao gồm/Loại bỏ (Include/Exclude)

Tại mỗi phần tử, 2 nhánh: chọn hoặc không chọn.

void combinationUtil(int arr[], int n, int r, int index, int comb[], int i) {
    if (index == r) { /* in comb */; return; }
    if (i >= n) return;
    comb[index] = arr[i];
    combinationUtil(arr, n, r, index + 1, comb, i + 1); // Chọn
    combinationUtil(arr, n, r, index, comb, i + 1);     // Không chọn
}

Kết quả (cả 2 phương pháp)

{ 1 2 3 } { 1 2 4 } { 1 2 5 } { 1 3 4 } { 1 3 5 } { 1 4 5 } { 2 3 4 } { 2 3 5 } { 2 4 5 } { 3 4 5 }

Độ phức tạp: O(C(n,r) × r) thời gian, O(r) stack space. C(n,r) = n!/(r!(n-r)!).