Print optimal solution for coin change algorithm

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, what is the optimal way to make change for N cents.

Example:

S = {2, 5, 10}
N = 6, then optimal solution is : 2, 2, 2

I have below working code:

public static void main(String argv[]) {
		long n = 10L;
		int[] combo = new int[100];
		int[] amounts = { 2, 5, 10 };
		ways(n, amounts, combo, 0, 0, 0);
	}

	public static void ways(long n, int[] amounts, int[] combo, int startIndex, int sum, int index) {
		if (sum == n) {
			printArray(combo, index);
		}

		if (sum > n) {
			return;
		}

		for (int i = 0; i < amounts.length; i++) {
			sum = sum + amounts[i];
			combo[index] = amounts[i];
			ways(n, amounts, combo, startIndex, sum, index + 1);
			sum = sum - amounts[i];
		}
	}

	public static void printArray(int[] combo, int index) {
		for (int i = 0; i < index; i++) {
			System.out.print(combo[i] + " ");
		}
		System.out.println();
	}

Output:

2 2 2 2 2 
5 5 
10 

Here I just need to optimal combination with less number of coins so only 10 in this example code.

But this code uses recursive approach, my value for N is Long type so as the value of N increases I am getting stackoverflow error.

The recursive approach I am following here is not correct, What is the correct way to solve this problem?

Update:

Based on MBo answer I tried below program, but I am not able to get the correct results:

static void testcase() {
		// make int array A of size N+1
		int N = 6;
		int[] A = new int[N + 1];
		// make int array P of size N+1
		int[] P = new int[N + 1];
		// fill A[] with large value (len(S) + 1)
		int[] S = { 2, 5, 10 };
		int lengthOfS = S.length;
		for (int i = 0; i < A.length; i++) {
			A[i] = lengthOfS + 1;
		}

		A[0] = 0;

		for (int s : S) {// coin value
			for (int i = s; i <= N; i++) {
				if (A[i - s] < A[i] + 1) { // using this coin we can get better
											// result for sum i
					A[i] = A[i - s] + 1;
					P[i] = s; // write down coin for this sum
				}
			}
		}
		System.out.println(Arrays.toString(P)); // [0, 0, 2, 2, 2, 5, 2]
		System.out.println(A[N]);// 3
		int idx = N;
		for (int i = 0; i < A[N]; i++) {
			int result = idx - P[idx];
			System.out.println(result); // 4 2 0
			idx = result;
		}
	}

This code prints:

[0, 0, 2, 2, 2, 5, 2]
3

4
2
0

How to fix this code?

For fixed set S = {2, 5, 10} solution is rather simple:

No solutions for N=1,3

if N is odd, you must use 5 - so N=N-5

Now use greedy approach: get as much 10-s as possible, then as much 2-s as possible

def best(N):
    print(N, end = ":  ")
    if (N % 2):
        print("5", end = "    ")
        N = N - 5
    if N >= 10:
        print("10*", N//10, end = "    ")
        N = N % 10
    if N > 1:
        print("2*", N//2, end = "    ")

21:  5    10* 1    2* 3    
22:  10* 2    2* 1    
23:  5    10* 1    2* 4    
24:  10* 2    2* 2    

In general you can find optimal solution using dynamic programming.

The first way is "memoization" - you have to implement recursive approach with the choice of the best solution, then add storing intermediate results in hashmap or another structure. Simple implementation:

S = [2, 3, 5, 7, 11]
dic = {}

def rec(summ):
    if summ == 0:
        return 0
    rd = dic.get(summ)
    if rd != None:
        return rd
    minn = 9999999999999
    for s in S:
        if s <= summ:
            minn = min(minn, 1 + rec(summ - s))
    dic[summ] = minn
    return minn
      
N = 1000
print(rec(N))

>>92

Another way is using table - you fill it with the best possible results using the first item, then update solution using the second item and so on.

Pseudocode

make int array A of size N+1
make int array P of size N+1
fill A[] with large value (MaxInt` or at least `N/min(S)) 
A[0] = 0
for s in S:  //coin value
    for (i = s; i <= N; i++)  
        if A[i - s] < A[i] + 1    //using this coin we can get better result for sum i
             A[i] = A[i - s] + 1
             P[i] = s            //write down coin for this sum

Now we have A[N] with the best count, and can retrieve needed coins using P[N], P[N - P[N]]... sequence.

Working Python code

S = [2, 3, 5, 7, 11]
N = 17
A = [0] + [10000] * N
P = [0] * (N + 1)
for s in S:  #coin value
    for i in range(s, N + 1):
        if A[i - s] < A[i] + 1:    #using this coin we can get better result for sum i
             A[i] = A[i - s] + 1
             P[i] = s            #write down coin for this sum

print(A) #for reference
i = N
while i > 0:
    print(P[i], end = " ")
    i = i - P[i]

>> [0, 10000, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 2, 3]
>> 11 3 3 

Note - if we can use every coin only once, we have to make inner loop in backward direction to avoid multiple adding the same coin

As the number of coins is small, and since the amount can be large, it is likely that backtracking can provide a good solution

Here is an implementation in C++
(Note: this code was already posted, but I can't find the post. Question deleted ?)

The coins are first sorted if descending order, to fasten the search.
In order to minimize the number of coins, we first try solutions with maximum possible number of coins of largest value.
In a given search, if the current number of coins is larger than the current minimum number of coins, we stopped the search ("premature abandon").

In the code, "UP" means that we will consider adding coins with a lower value

"DOWN" means that we will try to decrease the number of coins of higher value.

At a given step, we maintain an array corresponding to the number of coins for each coin value

#include    <iostream>
#include    <vector>
#include    <algorithm>
#include    <numeric>
//	The order of array coins is modified
std::vector<int> get_change(std::vector<int>& coins, int amount) {
std::vector<int> n_coins(coins.size(), 0);
std::vector<int> n_coins_opt(coins.size(), 0);
int n = coins.size();
std::sort(coins.begin(), coins.end(), std::greater<int>());
int sum = 0;    // current sum
int i = 0;      // index of the coin being examined
int n_min_coins = amount / coins[n - 1] + 1;
int n_total_coins = 0;
bool up_down = true;
while (true) {          // UP
if (up_down) {
n_coins[i] = (amount - sum) / coins[i];     // max possible number of coins[i]
sum += n_coins[i] * coins[i];
n_total_coins += n_coins[i];
if (sum == amount) {
if (n_total_coins < n_min_coins) {
n_min_coins = n_total_coins;
n_coins_opt = n_coins;
}
up_down = false;
sum -= n_coins[i] * coins[i];
n_total_coins -= n_coins[i];
n_coins[i] = 0;
i--;
}
else {
if (i == (n - 1) || (n_total_coins >= n_min_coins)) {   // premature abandon
sum -= n_coins[i] * coins[i];
n_total_coins -= n_coins[i];
n_coins[i] = 0;
up_down = false;
i--;
}
else {
i++;
}
}
}
else {            // DOWN
if (i < 0) break;
if (n_coins[i] == 0) {
if (i == 0) break;
i--;
}
else {
sum -= coins[i];
n_coins[i] --;
n_total_coins--;
i++;
up_down = true;
}
}
}
return n_coins_opt;
}
int main() {
std::vector<int> coins = {2, 5, 10};
int amount = 1731;
auto n_coins = get_change(coins, amount);
int sum = std::accumulate (n_coins.begin(), n_coins.end(), 0);
if (sum == 0) {
std::cout << "no solution\n";
} else {
std::cout << amount << " = ";
for (int i = 0; i < n_coins.size(); i++) {
std::cout << n_coins[i] << "*" << coins[i] << " ";
}
std::cout << "\n";
}
return 1;
}