Coin Change - Count Number of Ways of representing Amount given Finite supply of denominations

Problem

You are given:

• coins: An integer array representing coins of different denominations.
• counts: An integer array where counts[i] represents the maximum number of coins available for the denomination coins[i].
• amount: An integer representing the total amount of money to form.

You need to compute the number of distinct ways to form amount using the given denominations under the constraints that each denomination has a limited count.

Examples

Example 1

Input: coins = [1, 2], counts = [5, 2], amount = 5
Output: 4
Explanation: Possible combinations are:
1) [1, 1, 1, 1, 1]
2) [1, 1, 1, 2]
3) [1, 2, 2]
4) [2, 2, 1]
Hence, there are 4 ways to form the amount.

Example 2

Input: coins = [2, 3, 5], counts = [3, 1, 1], amount = 8
Output: 2
Explanation: Possible combinations are:
1) [3, 5]
2) [2, 2, 2, 2]
Hence, there are 2 ways to form the amount.

Solution

Method 1 - Using Recursion

The naive recursive approach involves trying all possible combinations of coins for each denomination while respecting their availability constraints (limited counts). It explores every possible way to form the amount using the given denominations and their respective counts.

Approach

• Base Case:
  • If amount == 0, return 1 (a valid way is found).
  • If amount < 0 or there are no denominations left, return 0 (not a valid way).
• Recursive Step:
  • For each denomination, try using it from 0 to counts[i] times and recursively solve the subproblem for the reduced amount and updated counts.

The naive recursive approach is inefficient due to overlapping subproblems, but it is useful for understanding the problem.

Code

C++

class Solution {
public:
    int helper(vector<int>& coins, vector<int>& counts, int index, int remaining) {
        // Base cases
        if (remaining == 0) return 1;
        if (remaining < 0 || index == coins.size()) return 0;
        
        int totalWays = 0;
        
        // Try using the current coin from 0 to counts[index] times
        for (int use = 0; use <= counts[index]; ++use) {
            totalWays += helper(coins, counts, index + 1, remaining - use * coins[index]);
        }
        
        return totalWays;
    }
    
    int numWaysRecursive(vector<int>& coins, vector<int>& counts, int amount) {
        return helper(coins, counts, 0, amount);
    }
};

// Example Usage
#include <iostream>
int main() {
    vector<int> coins = {1, 2};
    vector<int> counts = {5, 2};
    int amount = 5;
    
    Solution solution;
    cout << solution.numWaysRecursive(coins, counts, amount) << endl;  // Output: 4
}

Java

class Solution {
    public int helper(int[] coins, int[] counts, int index, int remaining) {
        // Base cases
        if (remaining == 0) {
            return 1;
        }
        if (remaining < 0 || index == coins.length) {
            return 0;
        }
        
        int totalWays = 0;
        
        // Try using the current coin from 0 to counts[index] times
        for (int use = 0; use <= counts[index]; use++) {
            totalWays += helper(coins, counts, index + 1, remaining - use * coins[index]);
        }
        
        return totalWays;
    }
    
    public int numWaysRecursive(int[] coins, int[] counts, int amount) {
        return helper(coins, counts, 0, amount);
    }

    // Example Usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = {1, 2};
        int[] counts = {5, 2};
        int amount = 5;
        System.out.println(solution.numWaysRecursive(coins, counts, amount)); // Output: 4
    }
}

Python

class Solution:
    def numWaysRecursive(self, coins, counts, amount):
        def helper(index, remaining):
            # Base cases
            if remaining == 0:
                return 1
            if remaining < 0 or index == len(coins):
                return 0
            
            total_ways = 0
            
            # Try using the current coin from 0 to counts[index] times
            for use in range(counts[index] + 1):
                total_ways += helper(index + 1, remaining - use * coins[index])
            
            return total_ways
        
        return helper(0, amount)

# Example Usage
coins = [1, 2]
counts = [5, 2]
amount = 5
solution = Solution()
print(solution.numWaysRecursive(coins, counts, amount))  # Output: 4

Complexity

• ⏰ Time complexity: O(counts[0] * counts[1] * ... * counts[n]), where n is the number of denominations. This is because we try every possible combination of coins.
• 🧺 Space complexity: O(amount), due to the recursion stack.

Method 2 - Using Top-down approach

The naive recursive approach can be optimised using memoization, which avoids recomputing overlapping subproblems. In this approach:

• Use a memo dictionary (or array) to store previously computed results for specific index and remaining values.
• This ensures that the function does not recompute the number of ways for the same state multiple times.

Algorithm

1. Define a recursive function helper(index, remaining) that calculates the number of ways to form the remaining amount using coins starting from the given index.
2. Use a dictionary or array memo to store computed results for (index, remaining) to avoid recomputation.
3. Modify the recursive approach:
   • Before computing the result for the current state (index, remaining), check whether it already exists in memo.
   • If it exists, return the stored result.
   • Otherwise, compute the result recursively, store it in memo, and return it.

Code

C++

class Solution {
public:
    int helper(vector<int>& coins, vector<int>& counts, int index, int remaining, unordered_map<string, int>& memo) {
        // Base cases
        if (remaining == 0) return 1;
        if (remaining < 0 || index == coins.size()) return 0;
        
        // Create a key for memoisation
        string key = to_string(index) + "," + to_string(remaining);
        
        // If already computed, return stored result
        if (memo.find(key) != memo.end()) {
            return memo[key];
        }
        
        int totalWays = 0;
        
        // Try using the current coin from 0 to counts[index] times
        for (int use = 0; use <= counts[index]; ++use) {
            totalWays += helper(coins, counts, index + 1, remaining - use * coins[index], memo);
        }
        
        // Store the result in memo
        memo[key] = totalWays;
        return totalWays;
    }
    
    int numWaysMemoization(vector<int>& coins, vector<int>& counts, int amount) {
        unordered_map<string, int> memo;  // Memoisation dictionary
        return helper(coins, counts, 0, amount, memo);
    }
};

// Example Usage
#include <iostream>
int main() {
    vector<int> coins = {1, 2};
    vector<int> counts = {5, 2};
    int amount = 5;
    
    Solution solution;
    cout << solution.numWaysMemoization(coins, counts, amount) << endl;  // Output: 4
}

Java

class Solution {
    public int helper(int[] coins, int[] counts, int index, int remaining, HashMap<String, Integer> memo) {
        // Base cases
        if (remaining == 0) {
            return 1; // Found a valid way
        }
        if (remaining < 0 || index == coins.length) {
            return 0; // No valid way
        }
        
        // Create a key for memoisation
        String key = index + "," + remaining;
        
        // If already computed, return stored result
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        int totalWays = 0;
        
        // Try using the current coin from 0 to counts[index] times
        for (int use = 0; use <= counts[index]; use++) {
            totalWays += helper(coins, counts, index + 1, remaining - use * coins[index], memo);
        }
        
        // Store the result in memo
        memo.put(key, totalWays);
        return totalWays;
    }
    
    public int numWaysMemoization(int[] coins, int[] counts, int amount) {
        HashMap<String, Integer> memo = new HashMap<>();  // Memoisation map
        return helper(coins, counts, 0, amount, memo);
    }

    // Example Usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = {1, 2};
        int[] counts = {5, 2};
        int amount = 5;
        System.out.println(solution.numWaysMemoization(coins, counts, amount)); // Output: 4
    }
}

Python

class Solution:
    def numWaysMemoization(self, coins, counts, amount):
        # Memo dictionary to store results of (index, remaining)
        memo = {}
        
        def helper(index, remaining):
            # Base cases
            if remaining == 0:
                return 1  # Found a valid way
            if remaining < 0 or index == len(coins):
                return 0  # No valid way
            
            # If already computed, return the stored result
            if (index, remaining) in memo:
                return memo[(index, remaining)]
            
            total_ways = 0
            
            # Try using the current coin from 0 to counts[index] times
            for use in range(counts[index] + 1):
                total_ways += helper(index + 1, remaining - use * coins[index])
            
            # Store the result in memo
            memo[(index, remaining)] = total_ways
            return total_ways
        
        return helper(0, amount)

# Example Usage
coins = [1, 2]
counts = [5, 2]
amount = 5
solution = Solution()
print(solution.numWaysMemoization(coins, counts, amount))  # Output: 4

Complexity

• ⏰ Time complexity: O(amount * len(coins) * max(counts))
  • len(coins) is the number of denominations.
  • max(counts) is the maximum number of repetitions we can try for each coin.
  • amount is the dimension of the memoisation table.
• 🧺 Space complexity: O(amount * len(coins))
  • Space is used for the memoisation table.
  • Maximum depth of recursion stack is O(len(coins).

Method 3 - Using bottom-up DP (1D array)

Reasoning or Intuition

1. This is a variation of the coin change problem with the additional constraint of limited counts for each denomination.
2. To solve it, we need to track both the amount we aim to form (amount) and the number of coins available for each denomination (counts).
3. A dynamic programming approach can be used:
   • Define a DP table dp[amount+1] where dp[i] represents the number of ways to form the amount i.
   • For each coin and its count, update the DP table by considering each valid usage of the coin (from 0 to counts[i]).

Approach

1. Construct an array dp where dp[i] denotes the number of distinct ways to form i.
2. Initialize dp[0] = 1 since there is one way to form amount 0 (by using no coins).
3. For every coin, iterate through the array dp in the reverse direction (to handle limited counts for each denomination).
4. For each amount j, iterate from 1 to counts[i] (representing the number of times we use the current coin) to calculate contributions.
5. Return dp[amount] as the final answer.

Code

C++

class Solution {
public:
    int numWays(vector<int>& coins, vector<int>& counts, int amount) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        
        for (int i = 0; i < coins.size(); ++i) {
            int coin = coins[i];
            int max_count = counts[i];
            
            for (int j = amount; j >= coin; --j) {
                for (int k = 1; k <= max_count; ++k) {
                    if (j - k * coin >= 0) {
                        dp[j] += dp[j - k * coin];
                    } else {
                        break;
                    }
                }
            }
        }
        
        return dp[amount];
    }
};

// Example Usage
#include <iostream>
int main() {
    vector<int> coins = {1, 2};
    vector<int> counts = {5, 2};
    int amount = 5;
    
    Solution solution;
    cout << solution.numWays(coins, counts, amount) << endl;  // Output: 4
}

Java

class Solution {
    public int numWays(int[] coins, int[] counts, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        
        for (int i = 0; i < coins.length; i++) {
            int coin = coins[i];
            int max_count = counts[i];
            
            for (int j = amount; j >= coin; j--) {
                for (int k = 1; k <= max_count; k++) {
                    if (j - k * coin >= 0) {
                        dp[j] += dp[j - k * coin];
                    } else {
                        break;
                    }
                }
            }
        }
        
        return dp[amount];
    }

    // Example Usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = {1, 2};
        int[] counts = {5, 2};
        int amount = 5;
        System.out.println(solution.numWays(coins, counts, amount));  // Output: 4
    }
}

Python

class Solution:
    def numWays(self, coins, counts, amount):
        dp = [0] * (amount + 1)
        dp[0] = 1
        
        for i in range(len(coins)):
            coin = coins[i]
            max_count = counts[i]
            
            for j in range(amount, coin - 1, -1):
                for k in range(1, max_count + 1):
                    if j - k * coin >= 0:
                        dp[j] += dp[j - k * coin]
                    else:
                        break
                        
        return dp[amount]

# Example Usage
coins = [1, 2]
counts = [5, 2]
amount = 5
solution = Solution()
print(solution.numWays(coins, counts, amount))  # Output: 4

Complexity

• ⏰ Time complexity: - O(amount * sum(counts)), where sum(counts) is the sum of maximum usages for all denominations.
• 🧺 Space complexity: - O(amount), because the dp array requires space proportional to the amount.