Проект Эйлера #31

Question

Описание проблемы:

В Англии валюта состоит из фунта, фунта стерлингов и пенса, р, и в обращении находится восемь монет:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

Сделать £2 можно следующим образом:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

Сколько разных способов можно заработать £2, используя любое количество монет?

Я попытался придумать свой собственный алгоритм для этого и потерпел неудачу. Итак, я наткнулся на этот (принятый ответ). Я попытался повторить это в C++ здесь. Когда я ввожу 1, 2 и 5 в combos() в функции main(), он дает правильный ответ, но 10 возвращает 11, когда должно быть 12. Что не так с моим алгоритмом?

#include <iostream>
#include <cstdlib>
using namespace std;

int coin[] = {1, 2, 5, 10, 20, 50, 100, 200};

/*Amounts entered must be in pence.*/
int combinations(int amount, int size) {
    int comboCount = 0;

    if(amount > 0) {
        if(size >= 0 && amount >= coin[size])
            comboCount += combinations(amount - coin[size], size);
        if(size > 0) //don't do if size is 0
            comboCount += combinations(amount, size-1);
    } else if(amount == 0)
        comboCount++;

    return comboCount;
}

int combos(int amount) {
    int i = 0;
    //get largest coin that fits
    for(i = 7; coin[i] > amount && i >= 0; i--); 
    return combinations(amount, i);
}

int main() {
    cout << "Answer: " << combos(10) << endl;
    return 0;
}

Answer 1

Ну, ваш код может вернуть 11, потому что это правильный ответ?

• http://ideone.com/uxv4J

Answer 2

(комментарий, на самом деле): Извините, но я вижу только 10 комбинаций для 10 пенсов из 1, 2 и 5:

10p:    0..5*2p + rest*1p     : 6 combinations
1x5p + 5p, that is
        0..2*2p + rest*1p     : 3 combinations
        1*5p                  : 1 combination