第一個版本（遞歸窮舉）

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

// 更新最佳方案的副本
// [out] _pCopy        副本
// [in] _pBest        最佳兌換方案
// [in] _nBest        最佳兌換方案所用鈔票數
void UpdateBestSchemeCopy(int*& _pCopy, int* _pBest, int _nUsed)
{
    if (_pCopy)
    {
        delete _pCopy;
    }

    _pCopy = new int[_nUsed];
    memcpy(_pCopy, _pBest, _nUsed * sizeof(int));;
}

// 打印數組
void PrintArray(int* _pArray, int num)
{
    printf("需要 %d 張鈔票：", num);
    for (int i = 0; i < num; i++)
    {
        printf("%d ", _pArray[i]);
    }
    printf("\n");
}

// 選擇兌現後張數最少的鈔票面值
// 
// [in] _nTotal        總金額
// [out] _pnBest    數組，存放最佳方案（用戶調用時傳入一個空指針即可）
// [in] _nIndexMin    內部使用，指定最小面值下標，防止重複的面值組合
// 
// 返回最佳方案所用的鈔票數
int ChooseParValue(int _nTotal, int*& _pnBest, int _nIndexMin = 0)
{
    // 記錄遞歸頭
    bool isHead = true;
    static bool isBody = false;
    if (!isBody)    isBody = true;    // 使位於後面的遞歸意識到自己不是頭部了
    else            isHead = false;

    // 所有可用面值（必須從大到小排列，且必須有 1 存在，暫時不處理沒有 1 的情況）
    static int pnParValues[] = { 103, 51, 13, 12, 9, 2, 1 };

    // 記錄當前方案
    static int nUsed = 0;
    static int* pnValuesUsed = nullptr;
    
    // 記錄最佳方案使用的鈔票張數
    static int nBestUsed = 0;

    // 在遞歸頭進行初始化
    if (isHead)
    {
        nUsed = 0;
        pnValuesUsed = new int[_nTotal];
        memset(pnValuesUsed, 0, _nTotal * sizeof(int));

        nBestUsed = _nTotal + 1;
    }

    // 由於在遞歸中，nUsed 會被深層遞歸修改，因此此處需要記錄到這一步已經用了幾張鈔票
    // 以便重置到當前狀態，換下一張鈔票重試
    int nHaveUsed_This = nUsed;    
    
    // 遍歷所有面值
    for (int i = _nIndexMin; i < sizeof(pnParValues) / sizeof(pnParValues[0]); i++)
    {
        // 跳過大於總金額的面值
        if (_nTotal < pnParValues[i])
        {
            continue;
        }

        pnValuesUsed[nHaveUsed_This] = pnParValues[i];
        nUsed = nHaveUsed_This + 1;                // 重置 nUsed

        // 已經兌換完成
        if (_nTotal == pnParValues[i])
        {
            // 輸出方案
            PrintArray(pnValuesUsed, nUsed);
            //_getch();

            // 判斷是不是更佳方案
            if (nUsed < nBestUsed)
            {
                UpdateBestSchemeCopy(_pnBest, pnValuesUsed, nUsed);
                nBestUsed = nUsed;
            }
        }
        // 繼續兌換
        else
        {
            // 此處傳入 i 作爲最小貨幣面值下標，是爲了防止重複的貨幣組合出現。
            // 如果一個組合 12 2 9 出現，那麼必然在它之前已經給出過 12 9 2 的組合，
            // 即爲了確保組合的唯一性，只需要確保 a1 >= a2 >= a3 以此類推。
            ChooseParValue(_nTotal - pnParValues[i], _pnBest, i);
        }
    }

    // 重置遞歸頭
    if (isHead)
        isBody = false;

    return nBestUsed;
}

int main()
{
    // 輸入需要兌換的金額總數，只接受整數
    unsigned int n = 0;
    scanf_s("%u", &n);        // 示例數據 24，貪心算法不是最優解

    int* pBestScheme = nullptr;
    int nBestNum = ChooseParValue(n, pBestScheme);

    printf("\n【最佳方案】\n");
    PrintArray(pBestScheme, nBestNum);

    return 0;
}