How many ways we can make the change of the amount using the coins given

Question

Given a set of coins and amount, write an algo­rithm to find out how many ways we can make the change of the amount using the coins given.

Exam­ple:

Amount = 5

coins [] = {1,2,3}

Ways to make change = 5

{1,1,1,1,1} {1,1,1,2}, {1,2,2}, {1,1,3} {2,3}

The code I've written works flawlessly, but the time complexity is too high. If you could suggest an improvement for this code or suggest a better approach, please let me know.

public class CoinChangeProblem {
    public static void main(String[] args) {

        calculatePossibleCombinations(0, 0);
        System.out.println("Answer : "+totalCombinations);

    }

    static int[] coins = { 1, 2, 3};
    static int amount = 5;

    static int totalCombinations= 0;    


    static void calculatePossibleCombinations(int pos, int sum)
    {
        if(pos< coins.length)
        {           
            int coin = coins[pos];          
            for(int j=0; j<=amount/coin && sum<=amount; j++)
            {
                calculatePossibleCombinations(pos+1, sum);
                sum = sum + coin;
                if(sum == amount)
                {
                    totalCombinations++; break;
                }
            }
        }
    }   
}

Answer 1

Got it working faster! Here's my updated code. I was able to use DP and memoize.

static int calculatePossibleCombinations(int pos, int amount)
{
    if(amount == 0)
    {
        return 1;
    }       

    if(pos < coins.length)
    {
        int ways = 0;
        int remainingAmount= 0;
        String key = pos + "-" + amount;

        if(memoizeMap.containsKey(key)) {
            return memoizeMap.get(key);
        }

        while(remainingAmount <= amount)
        {
            ways = ways + calculatePossibleCombinations(pos+1, amount- remainingAmount);
            remainingAmount = remainingAmount + coins[pos];
        }
        memoizeMap.put(key, ways);
        return ways;
    }
    return 0;
}