2
\$\begingroup\$

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;
                }
            }
        }
    }   
}
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.