0

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.

screamo
  • 19
  • 4
  • All your code paths leave `ways` at the 0 it receives, so there is nothing that would ever increment it – UnholySheep Nov 18 '22 at 19:51
  • hello, thank you. It becomes vector c when I use the coins – screamo Nov 18 '22 at 19:51
  • no I increment ways insde the recursive function – screamo Nov 18 '22 at 19:53
  • and yet `cout << "ways: " << ways << '\n';` always prints 0 - so I'll claim that you are wrong with your claim that it is incremented – UnholySheep Nov 18 '22 at 19:55
  • 2
    If you always pass in 0 for `ways`, what's the point of passing it at all? – user4581301 Nov 18 '22 at 19:57
  • ?? how can i solve it? – screamo Nov 18 '22 at 19:57
  • at each recursion, ways resets to 0 for that recursion, but when recursions unwind the ways for each recursion gets summed up to the previous recursion – screamo Nov 18 '22 at 19:59
  • Have you been introduced to debuggers? Being able to execute a program at your speed and watch exactly what happens in the program as it happens quickly disabuses any faulty assumptions that have been made. – user4581301 Nov 18 '22 at 19:59
  • yes i know debvuggers – screamo Nov 18 '22 at 20:00
  • That may be what you want to happen, but why waste the overhead and add noise by passing it? Just make a local variable and initialize it to zero. – user4581301 Nov 18 '22 at 20:00
  • [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Jesper Juhl Nov 18 '22 at 20:03
  • Look at the recursive exit condition. It returns `ways`, which can be no value other than 0. So the caller will add 0 to its 0 and get 0. Then it will return 0 to its caller, which will sum up another 0. Ultimately the function cannot return anything but 0. – user4581301 Nov 18 '22 at 20:05
  • if I don'5t do that but put the exit condition at the end of the function I am stuck in an infinite recursion loop – screamo Nov 18 '22 at 20:08
  • Every time you hit the end of the line and can actually make change, you have found 1 way. 1 appears to be a better value to return, if you have actually found a valid way to make change. If not, then return 0. – user4581301 Nov 18 '22 at 20:10
  • if I write return amount == 0; is what you say? still return 0 ... – screamo Nov 18 '22 at 20:20

1 Answers1

0

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;
Maciej Polański
  • 373
  • 1
  • 7