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

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);

}

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;
}
}
}
}
}

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;
}