For example, I have the following denominations
{5, 10, 20, 50}
The user input the amount they want to withdraw (e.g. 20), and the code will print out 4 because there are 4 ways to stack these bills to the sum of 20 (the maximum amount of bills is 5 and the order is irrelevant).
This is what my code looks like
#include <stdio.h>
#define DENOMINATIONS 4
#define MAX_BILLS 5
int denominations[DENOMINATIONS] = {5, 10, 20, 50};
int countWays(int amount, int index) {
if (amount == 0) {
return 1;
}
if (amount < 0 || index >= DENOMINATIONS) {
return 0;
}
int ways = 0;
for (int i = 0; i < MAX_BILLS && i * denominations[index] < amount; i++) {
ways += countWays(amount - denominations[index], index + 1);
}
return ways;
}
I thought it was okay, but the code doesn't work well with larger numbers such as 150 (where the expected result is 2 but the actual is 15) or 2700 (expected 0 but got 11)
At least these issues:
Insufficient subtraction
Subtract based on the number of bills used.
// ways += countWays(amount - denominations[index], index + 1);
ways += countWays(amount - i*denominations[index], index + 1);
OK to match the amount.
//for (int i = 0; i < MAX_BILLS && i * denominations[index] < amount; i++) {
for (int i = 0; i < MAX_BILLS && i * denominations[index] <= amount; i++) {
Best to test failure first
This test
if (amount == 0) {
return 1;
}
... should be after
if (amount < 0 || index >= DENOMINATIONS) {
return 0;
}
... to prevent an invalid index
from being counted as a solution.
Max number of bills needs clarity
OP's code limit the bill count to 5 per denomination.
If the total number of bills of all denominations is 5, then code needs to pass the bill count as part of countWays()
.
int countWays(int amount, int index, int bills_allowed) {