I have seen many answers related to this question but none that solves my problem. I know how to find the change but I want to know how to figure out the number of coins of each individual denomination required to come to that minimum. for example I have the following code in which target is the target amount, coins[] is the coin denominations given, len is the length of coins[]. qty[] is an empty array that I need. to fill with the number of coins in each denomination that we used to get to the result.
#include <stdio.h>
int make_change(const int coins[], int len, int target, int qty[]) {
assert(0 <= target && target <= COINS_MAX_TARGET);
assert(0 < len);
// table[i] will be storing the minimum number of coins
// required for i value. So table[V] will have result
int table[4096];
// Base case (If given value V is 0)
table[0] = 0;
// Initialize all table values as Infinite
for (int i=1; i<=target; i++) {
table[i] = 4095;
}
// Compute minimum coins required for all
// values from 1 to V
for (int i=1; i <= target; i++) {
// Go through all coins smaller than i
for (int j = 0; j < len; j++) {
if (coins[j] <= i) {
int sub_res = table[i-coins[j]];
if (sub_res != 4095 && sub_res + 1 < table[i]) {
table[i] = sub_res + 1;
}
}
}
}
for(int i = 0; i < len; i++) {
for(int j = i; i < len; i++) {
int temp_target = target - coins[i];
if(table[target]==4095)
return -1;
return table[target];
}