Coin Change II

January 10, 2025

Coin Change II: Counting Distinct Combinations

This problem involves finding the number of distinct combinations of coins that sum up to a given target amount.
It is a classic example of a Dynamic Programming (DP) problem, focusing on combinations rather than permutations.

Problem Description : Coin Change ||

You are given:

An integer array coins where each element represents the denomination of a coin (e.g., 1, 5, 10, etc.).
An integer amount representing the target sum.

Objective: Return the number of distinct combinations of coins that sum up to amount. If it’s impossible to reach the amount, return 0.

Problem Breakdown

Input: 2D grid of non-negative integers.
Objective: Find the length of the longest strictly increasing path.
Movement: Can move to adjacent cells (up, down, left, right) but not diagonally.
Constraints: Each move must go to a cell with a strictly greater value.
Goal: Determine the longest path by efficiently exploring the grid.

Explanation:

1+1+1+1 = 4
1+1+2 = 4
2+2 = 4
1+3 = 4

Example 2

Input: amount = 7, coins = [2,4]

Output: 0

Constraints:

1 <= coins[i] <= 1000
1 <= coins.length <= 100
0 <= amount <= 1000

There are mainly three approach to solve this problem –

Recursion
Dynamic Programming (Top-Down)
Dynamic Programming (Bottom-up)

1. Recursion

Python

C++

Java

JavaScript

Python

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        coins.sort()
        memo = [[-1] * (amount + 1) for _ in range(len(coins) + 1)]

        def dfs(i, a):
            if a == 0:
                return 1
            if i >= len(coins):
                return 0
            if memo[i][a] != -1:
                return memo[i][a]
            
            res = 0
            if a >= coins[i]:
                res = dfs(i + 1, a)
                res += dfs(i, a - coins[i])

            memo[i][a] = res
            return res

        return dfs(0, amount)

C++

class Solution {
public:
    int change(int amount, vector& coins) {
        sort(coins.begin(), coins.end());
        return dfs(coins, 0, amount);
    }

private:
    int dfs(const vector& coins, int i, int a) {
        if (a == 0) {
            return 1;
        }
        if (i >= coins.size()) {
            return 0;
        }

        int res = 0;
        if (a >= coins[i]) {
            res = dfs(coins, i + 1, a);
            res += dfs(coins, i, a - coins[i]);
        }
        return res;
    }
};

Java

public class Solution {
    public int change(int amount, int[] coins) {
        Arrays.sort(coins);

        return dfs(coins, 0, amount);
    }

    private int dfs(int[] coins, int i, int a) {
        if (a == 0) {
            return 1;
        }
        if (i >= coins.length) {
            return 0;
        }

        int res = 0;
        if (a >= coins[i]) {
            res = dfs(coins, i + 1, a);
            res += dfs(coins, i, a - coins[i]);
        }
        return res;
    }
}

JavaScript

class Solution {
    /**
     * @param {number} amount
     * @param {number[]} coins
     * @return {number}
     */
    change(amount, coins) {
        coins.sort((a, b) => a - b);
    
        const dfs = (i, a) => {
            if (a === 0) return 1;
            if (i >= coins.length) return 0;

            let res = 0;
            if (a >= coins[i]) {
                res = dfs(i + 1, a);
                res += dfs(i, a - coins[i]);
            }
            return res;
        };

        return dfs(0, amount);
    }
}

2. Dynamic Programming (Top-Down)

Time & Space Complexity

Time complexity:
Space complexity:

Python

Java

C++

JavaScript

Python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        dp = {}  # (r, c) -> LIP

        def dfs(r, c, prevVal):
            if (r < 0 or r == ROWS or c < 0 or 
                c == COLS or matrix[r][c] <= prevVal
            ):
                return 0
            if (r, c) in dp:
                return dp[(r, c)]

            res = 1
            res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
            res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
            dp[(r, c)] = res
            return res

        for r in range(ROWS):
            for c in range(COLS):
                dfs(r, c, -1)
        return max(dp.values())

Java

public class Solution {
    public int change(int amount, int[] coins) {
        Arrays.sort(coins);
        int[][] memo = new int[coins.length + 1][amount + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return dfs(0, amount, coins, memo);
    }

    private int dfs(int i, int a, int[] coins, int[][] memo) {
        if (a == 0) return 1;
        if (i >= coins.length) return 0;
        if (memo[i][a] != -1) return memo[i][a];

        int res = 0;
        if (a >= coins[i]) {
            res = dfs(i + 1, a, coins, memo);
            res += dfs(i, a - coins[i], coins, memo);
        }
        memo[i][a] = res;
        return res;
    }
}

C++

class Solution {
public:
    int change(int amount, vector& coins) {
        sort(coins.begin(), coins.end());
        vector> memo(coins.size() + 1, 
                            vector(amount + 1, -1));

        return dfs(0, amount, coins, memo);
    }

    int dfs(int i, int a, vector& coins, vector>& memo) {
        if (a == 0) return 1;
        if (i >= coins.size()) return 0;
        if (memo[i][a] != -1) return memo[i][a];

        int res = 0;
        if (a >= coins[i]) {
            res = dfs(i + 1, a, coins, memo);
            res += dfs(i, a - coins[i], coins, memo);
        }
        memo[i][a] = res;
        return res;
    }
};

JavaScript

class Solution {
    /**
     * @param {number} amount
     * @param {number[]} coins
     * @return {number}
     */
    change(amount, coins) {
        coins.sort((a, b) => a - b);
        let memo = Array.from({ length: coins.length + 1 }, () =>
                   Array(amount + 1).fill(-1));

        const dfs = (i, a) => {
            if (a === 0) return 1;
            if (i >= coins.length) return 0;
            if (memo[i][a] !== -1) return memo[i][a];

            let res = 0;
            if (a >= coins[i]) {
                res = dfs(i + 1, a);
                res += dfs(i, a - coins[i]);
            }
            memo[i][a] = res;
            return res;
        };

        return dfs(0, amount);
    }
}

3. Dynamic Programming (Bottom-Up)

Time & Space Complexity

Time complexity:
Space complexity:

Python

Java

C++

JavaScript

Python

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        coins.sort()
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        
        for i in range(n + 1):
            dp[i][0] = 1
        
        for i in range(n - 1, -1, -1):
            for a in range(amount + 1):
                if a >= coins[i]:
                    dp[i][a] = dp[i + 1][a]  
                    dp[i][a] += dp[i][a - coins[i]]  

        return dp[0][amount]

Java

public class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        Arrays.sort(coins);
        int[][] dp = new int[n + 1][amount + 1];

        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int a = 0; a <= amount; a++) {
                if (a >= coins[i]) {
                    dp[i][a] = dp[i + 1][a];
                    dp[i][a] += dp[i][a - coins[i]];
                }
            }
        }

        return dp[0][amount];
    }
}

C++

class Solution {
public:
    int change(int amount, vector& coins) {
        int n = coins.size();
        sort(coins.begin(), coins.end());
        vector> dp(n + 1, vector(amount + 1, 0));
        
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int a = 0; a <= amount; a++) {
                if (a >= coins[i]) {
                    dp[i][a] = dp[i + 1][a];
                    dp[i][a] += dp[i][a - coins[i]];
                }
            }
        }

        return dp[0][amount];
    }
};

JavaScript

class Solution {
    /**
     * @param {number} amount
     * @param {number[]} coins
     * @return {number}
     */
    change(amount, coins) {
        coins.sort((a, b) => a - b);
        const n = coins.length;
        const dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(0));

        for (let i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (let i = n - 1; i >= 0; i--) {
            for (let a = 0; a <= amount; a++) {
                if (a >= coins[i]) {
                    dp[i][a] = dp[i + 1][a];
                    dp[i][a] += dp[i][a - coins[i]];
                }
            }
        }

        return dp[0][amount];
    }
}