参考答案

#include "stdafx.h"

using namespace std;
int count = 0;
int Target = 0;
int coin[4] = {1, 2, 5, 10};
int total = 0;
vector solution;
void dfs(int index)
{
    if ( total == Target )
    {
        count++;
        cout << count << ":" ;
        for ( int i = 0; i < (int)solution.size(); i++)
        {
            cout << solution[i] << " ";
        }
        cout << endl;
        return;
    }
    if ( total > Target )
        return;
    for ( int i = index; i < 4; i++)
    {
        total += coin[i];
        solution.push_back( coin[i] );
        dfs(i);
        solution.pop_back();
        total -= coin[i];
    }
}
int _tmain(int argc, _TCHAR *argv[])
{
    while (1)
    {
        count = 0;
        cin >> Target;
        dfs(0);
        cout << count << endl;
    }
    return 0;
}