#include <stdio.h>
#include <stdlib.h>
// Function to find the total number of combinations to make amount
long totalCombinations(int coins[], int num_coins, int amount) {
long *arr = (long *)malloc((amount + 1) * sizeof(long));
if (arr == NULL) {
printf("Memory allocation failed.\n");
return -1;
}
// Initialize the array to 0
for (int i = 0; i <= amount; i++) {
arr[i] = 0;
}
// Base case: There is one way to make an amount of 0 (using no coins)
arr[0] = 1;
// Iterate through all coins one by one
for (int i = 0; i < num_coins; i++) {
for (int j = coins[i]; j <= amount; j++) {
arr[j] += arr[j - coins[i]];
}
}
long result = arr[amount];
free(arr);
return result;
}
int main() {
int coins[] = {1, 2, 5};
int num_coins = sizeof(coins) / sizeof(coins[0]);
int amount = 6;
// [1, 5], [1, 1, 1, 1, 1, 1], [2, 2, 2], [1, 1, 1, 1, 2], [2, 2, 1, 1]
printf("For amount = %d and coins = {1, 2, 5}:\n", amount);
printf("Total combinations: %ld\n\n", totalCombinations(coins, num_coins, amount));
int coins2[] = {2, 5, 10};
int num_coins2 = sizeof(coins2) / sizeof(coins2[0]);
amount = 10;
// [5, 5], [2, 2, 2, 2, 2], [10]
printf("For amount = %d and coins = {2, 5, 10}:\n", amount);
printf("Total combinations: %ld\n", totalCombinations(coins2, num_coins2, amount));
return 0;
}
/*
run:
For amount = 6 and coins = {1, 2, 5}:
Total combinations: 5
For amount = 10 and coins = {2, 5, 10}:
Total combinations: 3
*/
