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 &lt;= target) { //if it is greater than the target then why recurse???
                int c = makeChangeBacktracking(sum, coins, target, count + 1, minCoins);
                if(minCoins &gt; 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.
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

Does this solve your problem?  

e.g   Available coins: 1p,2p,5p,10p,20p,50p,£1 ...
47p -> -20p -> 27p -> -20p -> 17p -> -10p -> 7p -> -5p -> 2p -> -2p -> 0p

There are other less efficient ways to do this like maybe using genetic algorithms but I guess this would be the quickest ...