Coin change problem in C stuck on recursion-CodePudding

I have to write a recursiive solution to the coin change problem in C . The problem provides a set of coins of different values and a value representing a sum to be paid. The problem asks to provide the number of ways in which the sum can be paid given the coinages at hand.

I am stuck on this:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long recursive(int amount, vector<long>& input_vector, long ways, vector<long>::const_iterator current) { 
    if (amount < 0)
        return ways;
    for (auto iter = current; iter != input_vector.end();   iter) {
        cout << "amount: " << amount << ", current coin: " << *iter << '\n';
        ways  = recursive(amount - *iter, input_vector, 0, iter);
        cout << "ways: " << ways << '\n';
    }
    return ways;
}

long getWays(int n, vector<long> c) {
    sort(c.begin(), c.end(), greater<long>());
    
    return recursive(n, c, 0, c.begin());
}

int main() {
    int amount = 32;
    vector<long> coinages = {2, 5, 6, 10};
    
    cout << "Solution is: " << getWays(amount, coinages) << endl;
    
    return 0;
}

The answer should be 27, but I get 0? Even if I omit the eturn 0 at the end of the main program, I still get 0. So I'm kind of frustrated my logic does not work here and I'm clueless about how to solve this in a different way.

CodePudding user response：

If amount is 0, this is an answer, return 1 to be added to ways. If you got below 0, dead end street, return 0, nothing will be added.

if (amount == 0)
    return 1;
if (amount < 0)
    return 0;