遞迴練習：換零錢組合數統計（硬幣找零問題 C++ 實作）

遞迴演算法進階練習：統計換零錢的組合方式數（硬幣找零問題）

經典組合數學問題：給定面額為 50、25、10、5、1 的硬幣（各無限枚），求湊出總金額 N 的不同組合數。順序不重要，即 {50, 25, 25} 與 {25, 50, 25} 視為同一種組合。

遞迴策略：決策樹 + 狀態壓縮

對每種面額，有兩種選擇：使用該面額 或 不再使用該面額（換下一種）。透過 flag 標記某面額是否仍可用，避免重複計數。

資料結構設計

typedef struct {
    int value;   // 面額
    int flag;    // 是否仍可使用 (1=可用, 0=禁用)
} coin_t;

typedef struct {
    coin_t c50, c25, c10, c5, c1;
} coins_t;

核心遞迴函數

static int countWays(int amount, coins_t coins) {
    if (amount == 0) return 1;      // 找到一種有效組合
    if (amount < 0) return 0;       // 超額，無效
    
    // 依面額從大到小決策
    if (coins.c50.flag) {
        if (onlyCoinLeft(coins, 50)) return 1;
        coins_t next = coins; next.c50.flag = 0;
        return countWays(amount, next)           // 不用 50
             + countWays(amount - 50, coins);    // 用 50（可重複用）
    }
    // 25, 10, 5, 1 同理...
    // 略
}

輔助函數：判斷是否只剩單一面額

static int onlyCoinLeft(coins_t &c, int denom) {
    // 檢查除 denom 外所有 flag 是否為 0
    // 例如 denom=25：c50.flag==0 && c10.flag==0 && c5.flag==0 && c1.flag==0
}

完整程式碼結構

int main() {
    coins_t coins = {{50,1},{25,1},{10,1},{5,1},{1,1}};
    cout << "ways(100) = " << countWays(100, coins) << endl;
    return 0;
}

複雜度與優化方向

• 時間複雜度：指數級，適用於小金額教學示範
• 實際工程建議：動態規劃 (DP)，dp[i] 表示湊出金額 i 的方法數，單層迴圈 O(N×幣種數) 解決
• 記憶化搜尋：對 (amount, coins_state) 快取結果，大幅剪枝

核心收穫

1. 遞迴解決組合計數問題的「選/不選」決策模式
2. 狀態標記（flag）避免排列重複計數的技巧
3. 理解遞迴邊界條件：amount==0 成功、amount<0 失敗、無可用硬幣 失敗
4. 認識遞迴效率瓶頸，自然引向 DP 優化思路

這道題目是從「會寫遞迴」邁向「理解組合優化」的絕佳橋樑。