組合生成算法：遞歸實現 n 選 k 的所有組合

問題定義

給定 n 個互不相同元素，求所有選取 k 個元素的組合（順序無關）。例如 {1,2,3,4} 選 2：{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}。

遞歸思路

「以某元素為首」+「從其後元素中選 k-1 個」。

combine([1,2,3,4], 2)
= 1 + combine([2,3,4], 1)
= 2 + combine([3,4], 1)
= 3 + combine([4],   1)
= 4 + combine([],    1) → 終止（剩餘不足）

代碼實現

#include <stdio.h>
#include <string.h>

#define MAX_N 20

int g_combination[MAX_N];
int g_top = 0;

// 打印當前組合
void print_combination() {
    for (int i = 0; i < g_top; ++i)
        printf("%d ", g_combination[i]);
    printf("\n");
}

// 遞歸生成
// data: 待選元素陣列起始位址
// len:  待選元素個數
// k:    尚需選取個數
void combine(int data[], int len, int k) {
    if (k == 0) {           // 已選夠 k 個
        print_combination();
        return;
    }
    if (len < k) return;    // 剩餘元素不足，剪枝

    for (int i = 0; i < len; ++i) {
        g_combination[g_top++] = data[i];           // 選擇 data[i]
        combine(data + i + 1, len - i - 1, k - 1);  // 從後續元素選 k-1
        --g_top;                                    // 回溯
    }
}

int main() {
    int data[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(data) / sizeof(int);
    int k = 4;

    memset(g_combination, 0, sizeof(g_combination));
    combine(data, n, k);
    return 0;
}

關鍵點解析

1. 全局緩衝區 g_combination 記錄當前路徑，g_top 模擬堆疊指標。
2. 遞歸參數縮減：data + i + 1 確保不重複、不倒序；len - i - 1 更新剩餘可選數量；k - 1 更新仍需選取數。
3. 剪枝優化：if (len < k) return; 避免無效遞歸。
4. 終止條件：k == 0 表示組合完成，打印結果。

複雜度

• 時間：O(C(n,k) * k) —— 每個組合輸出需 O(k)。
• 空間：O(k) 遞歸深度 + O(k) 全局緩衝區。

測試驗證

修改 data 與 k，對照數學計算結果：

• n=4, k=2 → 6 組
• n=6, k=4 → 15 組
• n=5, k=5 → 1 組（全選）

擴展應用

• 排列生成：移除 data + i + 1 限制，改用 used[] 標記數組。
• 子集生成：k 從 0 到 n 依次調用，或單次遞歸在每層決定「選/不選」。
• 組合總和/子集和：在遞歸中累加和，滿足條件時記錄。

總結

組合生成是回溯法的經典入門。核心模板：選擇 → 遞歸 → 撤銷選擇。掌握此模式，可解決 LeetCode 77、39、40 等大類組合/子集問題。