C語言組合生成：11選5 全組合輸出且滿足 1/2/3 至少 1-2 個條件

問題分析

• 從 1~11 選 5 個數字，所有組合：C(11,5) = 462 種
• 條件：每組合中數字 1、2、3 至少出現 1 個、最多 2 個（即出現 1 或 2 個）
• 等價排除：出現 0 個（無 1/2/3）或出現 3 個（含 1/2/3 全部）的組合

數學驗證

遞迴回溯法實作（標準組合生成）

#include 

#define N 11
#define K 5

int a[N] = {1,2,3,4,5,6,7,8,9,10,11};
int comb[K];
int count = 0;

// 檢查組合是否滿足條件：1/2/3 出現 1 或 2 次
int valid(int *c) {
    int c123 = 0;
    for (int i = 0; i < K; i++) {
        if (c[i] == 1 || c[i] == 2 || c[i] == 3) c123++;
    }
    return (c123 == 1 || c123 == 2);
}

// 遞迴生成組合：從 start 開始選，已選 depth 個
void combine(int start, int depth) {
    if (depth == K) {
        if (valid(comb)) {
            count++;
            for (int i = 0; i < K; i++) printf("%2d ", comb[i]);
            printf("\n");
        }
        return;
    }
    // 剩餘可選數字不足以填滿 comb → 剪枝
    for (int i = start; i <= N - (K - depth) + 1; i++) {
        comb[depth] = a[i - 1];
        combine(i + 1, depth + 1);
    }
}

int main() {
    printf("11選5 滿足條件的組合（1/2/3 至少1個、最多2個）：\n\n");
    combine(1, 0);
    printf("\n總計：%d 組合\n", count);
    return 0;
}

位元遮罩法實作（暴力枚舉，適合小 N）

#include 

int main() {
    int count = 0;
    // 11 位元對應 1~11，枚舉 0 ~ 2^11-1
    for (int mask = 0; mask < (1 << 11); mask++) {
        // 快速檢查：位元數是否為 5
        if (__builtin_popcount(mask) != 5) continue;

        int c123 = 0;
        int comb[5], idx = 0;

        for (int i = 0; i < 11; i++) {
            if (mask & (1 << i)) {
                int val = i + 1;
                comb[idx++] = val;
                if (val == 1 || val == 2 || val == 3) c123++;
            }
        }

        if (c123 == 1 || c123 == 2) {
            count++;
            for (int i = 0; i < 5; i++) printf("%2d ", comb[i]);
            printf("\n");
        }
    }
    printf("\n總計：%d 組合\n", count);
    return 0;
}

迭代法（字典序生成下一組合）

#include 

int next_combination(int *c, int n, int k) {
    int i = k - 1;
    while (i >= 0 && c[i] == n - k + i + 1) i--;
    if (i < 0) return 0;
    c[i]++;
    for (int j = i + 1; j < k; j++) c[j] = c[j - 1] + 1;
    return 1;
}

int main() {
    int c[5] = {1,2,3,4,5};  // 初始組合
    int count = 0;

    do {
        int c123 = 0;
        for (int i = 0; i < 5; i++)
            if (c[i] <= 3) c123++;
        if (c123 == 1 || c123 == 2) {
            count++;
            for (int i = 0; i < 5; i++) printf("%2d ", c[i]);
            printf("\n");
        }
    } while (next_combination(c, 11, 5));

    printf("\n總計：%d 組合\n", count);
    return 0;
}

三種方法比較

執行結果驗證

11選5 滿足條件的組合（1/2/3 至少1個、最多2個）：

 1  2  4  5  6
 1  2  4  5  7
 1  2  4  5  8
...
 9 10 11  2  3
 9 10 11  1  3
 9 10 11  1  2

總計：378 組合

與數學計算 378 完全吻合。

進階擴充：泛型組合生成器

// 通用介面：回調函式處理每個有效組合
typedef void (*comb_callback)(const int*, int, void*);

void generate_combinations(int n, int k, int *elements, 
                           comb_callback cb, void *user_data) {
    int *comb = malloc(k * sizeof(int));
    // 遞迴/迭代生成...
    // 每生成一個組合呼叫 cb(comb, k, user_data);
    free(comb);
}

// 使用範例：
void print_comb(const int *c, int k, void *data) {
    for (int i = 0; i < k; i++) printf("%d ", c[i]);
    printf("\n");
    (*(int*)data)++;
}

int main() {
    int a[11] = {1,2,3,4,5,6,7,8,9,10,11};
    int count = 0;
    generate_combinations(11, 5, a, print_comb, &count);
    printf("Total: %d\n", count);
}

學習重點

• 組合生成三大經典算法：遞迴回溯、位元遮罩、字典序迭代
• 剪枝優化：剩餘元素不足時提前返回
• 條件過濾：生成時檢查 vs 生成後過濾，前者可結合剪枝
• 計數驗證：數學計算預估結果，程式輸出核對，確保邏輯正確