演算法實作筆記：遞迴實現組合生成（資料選擇問題）

問題描述

給定一組互不相同的資料元素（例如 {1, 2, 3, 4}），要求從中選取 k 個元素，列出所有可能的組合（順序不計，即 {1,2} 與 {2,1} 視為相同）。這是經典的「組合生成」問題，數學表示為 C(n, k)。

遞迴思路解析

採用「決策樹」視角：對於當前位置 i，我們有兩種選擇——選 或 不選。但為了避免重複組合，約定只能從當前位置之後的元素中繼續選擇。具體步驟：

1. 從索引 start 開始遍歷陣列；
2. 將 data[start] 加入當前組合路徑；
3. 若路徑長度達到 k，輸出該組合；
4. 否則，遞迴處理 start+1 及之後的元素，需再選 k-1 個；
5. 回溯：將 data[start] 從路徑移除，繼續迴圈嘗試下一個起始元素。
6. 終止條件：剩餘元素數量 < 尚需選取數量，直接返回。

程式碼實作（C 語言）

全域狀態與輔助函數

#define MAX_N 100

static int g_combination[MAX_N];  // 記錄當前組合路徑
static int g_top = 0;             // 路徑長度（棧頂指標）

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

核心遞迴函數

// data: 來源資料陣列
// len:  從 data[0] 開始的有效長度
// need: 還需要選取的元素個數
void combine(const int *data, int len, int need) {
    if (need == 0) {                 // 已選夠 k 個
        print_combination();
        return;
    }
    if (len < need) return;          // 剩餘元素不足，剪枝

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

測試驅動

void test_combine(void) {
    int data[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(data) / sizeof(data[0]);
    g_top = 0;
    combine(data, n, 4);   // 從 6 個元素中選 4 個
}

關鍵點總結

• 避免重複：遞迴時傳遞 data + i + 1，確保後續選擇嚴格在當前元素之後，自然保證組合升序、無重複。
• 剪枝優化：if (len < need) return; 提前終止無效遞迴，大幅減少呼叫次數。
• 棧深度：最大遞迴深度為 k，配合靜態陣列 g_combination 避免頻繁動態分配。
• 泛化性：將 int 改為 void* 並配合比較函數指標，即可處理任意型別資料。

延伸思考

若需生成「排列」（順序敏感），只需移除「只能從後續選擇」的限制，改為對所有未使用元素嘗試，並用 bool used[] 標記即可。組合生成是回溯法最經典的入門範例，掌握其「選/不選 + 狀態回溯」模板，可輕鬆擴展至子集生成、分割問題、N 皇后等眾多搜尋問題。