# Can the algorithm be optimized?

I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach with mermoization and a bottom up using dynamic programming. Even the brute force apporach always starts using a top down approach breaking the problem down into smaller sub problems and then caching.

However, I have written the following algorithm that is not optimized to do the same but cannot figure out how to apply memoization. Is it even possible?

My basic algorithm is I start from sum = 0 and keep count of how many coins I have used by adding coin values and then returning the minimum count.

//function is called with sum = 0, coins = 0 and minCoins = Integer.MAX_VALUE
//coins[] contains the different coin denominations and target is the desired amount
// count is the number of coins that have been used

public static int makeChangeBacktracking(int sum, int[] coins, int target, int count, int minCoins) {

if(sum == target) {
return count;
}

for(int coin : coins) {
//choose
sum+= coin;
//explore
if(sum <= target) { //if it is greater than the target then why recurse???
int c = makeChangeBacktracking(sum, coins, target, count + 1, minCoins);
if(minCoins > c) {
minCoins = c;
}
//undo
sum-= coin;
}
}
return minCoins;
}


I would like to apply any technique to improve the run time of the above algorithm. A clear explanation of whether or not memoization or other optimization techniques can be applied to this to speed up would be helpful.

• This problem is known as the Change-making Problem. See the related wikipage: en.wikipedia.org/wiki/Change-making_problem . Jun 8 '20 at 11:28
• Thanks but the link doesn't explain going from sum 0 and then picking coins and any optimization for it. Can you provide an explanation? Jun 8 '20 at 12:27
• Currently the fastest solutions to the unbounded change-making problem are branch-and-bound algorithms with additional optimizations (such as partial/full memoization). See here for one example: stackoverflow.com/a/45121962/109122 Oct 15 at 12:03

A simple and efficient algorithm would be (correct me if I'm wrong):

1) Find the biggest valued coin just below that particular amount
2) Do the same thing with amount - coin_chosen
3) Repeat until convergence

• This is a greedy algorithm where its correctness depends on the available coins. Consider the coin set $\{1,4,9\}$ and the target sum of 12. By your approach, we need 4 coins: one 9, three times 1. The optimal number is 3 coins. Jun 8 '20 at 11:25