Valizada's blog

518. Coin Change 2 - June day 7

link to leetcode problem definition

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Example 1

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Recursion - all permutations

We can solve this problem recursively. Let result(x) denote the number of ways we can form the amount x. For example, if coins = {1, 2, 5}, then result(4) = 5 and the recursive formula is:

result(x) = result(x-1) + result(x-2) + result(x-5)

Our base cases:

  1. x = 0, return 1 - Essentially we subtracted (used) all coins, hence one permutation
  2. x < 0, return 0

This gives us all the possibilities including duplicates, permutations.

See an example of recursion tree for amount 4 (please note I omitted negative paths to shorten the tree): amount4

class Solution {
    private int[] coins;
    public int change(int amount, int[] coins) {
        this.coins = coins;
        return result(amount);
    }
    
    private int result(int amount) {
        if(amount == 0) {
            return 1;
        }
        
        if(amount < 0) {
            return 0;
        }
        
        int res = 0;
        for (int i = 0; i < coins.length; i++) {
            res += result(amount - coins[i]);
        }
        return res;
    }
}

Recursion - all combinations

To get combinations, we need to keep the track of the coin that is currently being used and do not repeat it. To achieve this we can pass the current coin as argument to our function. Notice that we need to start iteration of coins from the given coin by excluding already calculated ones:

class Solution {
    private int[] coins;
    public int change(int amount, int[] coins) {
        this.coins = coins;
        return result(amount, 0);
    }
    
    private int result(int amount, int coin) {
        if(amount == 0) {
            return 1;
        }
        
        if(amount < 0) {
            return 0;
        }
        
        int res = 0;
        for (int i = coin; i < coins.length; i++) {
            res += result(amount - coins[i], i);
        }
        return res;
    }
}

This solution will run in exponential time, see next section on how to optimise it.

Recursion - memoization

To optimise the solution we can add memoisation step to store results per amount and the given coin.

class Solution {
    private int[] coins;
    private int[][] memo;
    public int change(int amount, int[] coins) {
        this.coins = coins;
        this.memo = new int[amount + 1][coins.length + 1];
        
        Arrays.stream(memo).forEach(a -> Arrays.fill(a, -1));
        return result(amount, 0);
    }
    
    private int result(int amount, int coin) {        
        if(amount < 0) {
            return 0;
        }
        
        if(amount == 0) {
            return 1;
        }
        
        if(memo[amount][coin] != -1) {
            return memo[amount][coin];
        }
        
        int res = 0;
        for (int i = coin; i < coins.length; i++) {
            res += result(amount - coins[i], i);
        }
        memo[amount][coin] = res;
        return res;
    }
}

Dynamic programming - all permutations

Let's transform top-down approach with memoization to bottom-up:

class Solution {

    public int change(int amount, int[] coins) {     
        var dp = new int[amount + 1];
        dp[0] = 1;
        
        for(int i = 1; i <= amount; i++) {
            for(int coin : coins) {
                if(i >= coin) {
                    dp[i] += dp[i - coin];   
                }
            }
        }
        
        return dp[amount];
    }
}

Dynamic programming - all combinations

Just flip the order of the loops and we get a solution for combinations (without duplicates)

class Solution {

    public int change(int amount, int[] coins) {     
        var dp = new int[amount + 1];
        dp[0] = 1;
        
        for(int coin : coins) {
            for(int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        
        return dp[amount];
    }
}