Katkat
Back

Count ways to make change (DP)

Walmart LabsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests the ability to solve the classic 'Coin Change II' problem using dynamic programming to count the number of unique combinations that sum up to a target amount.

Problem Statement

You are given an integer amount representing the total value of money and an array of integers coins representing the denominations of different coins. Each denomination can be used an unlimited number of times. Write a function to calculate the number of unique combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that there are infinite supply of each coin and that each combination is order-independent (e.g., 1 + 2 is the same as 2 + 1).

Function Signature

def count_change_combinations(amount: int, coins: List[int]) -> int:

Constraints

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • 0 <= amount <= 5000

Examples

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

  1. 5=5
  2. 5=2+2+1
  3. 5=2+1+1+1
  4. 5=1+1+1+1+1

Example 2: Input: amount = 3, coins = [2] Output: 0 Explanation: The amount of 3 cannot be made up with only 2s.

Edge Cases

  • amount = 0: Should return 1 (there is one way to make 0: using no coins).
  • Empty coins array: Should return 0 if amount > 0.

Hints

Hint 1

Define a DP array `dp` where `dp[i]` stores the number of ways to make the amount `i` using the coins processed so far.

Hint 2

Initialize `dp[0] = 1` because there is exactly one way to make the amount 0, and all other `dp` indices to 0.

Hint 3

For each coin in the input list, iterate through the `dp` array starting from the coin's value up to the total amount, adding `dp[i - coin]` to `dp[i]`.

Follow-up questions

  • How would you modify the solution if the order of coins matters (e.g., [1, 2] is different from [2, 1])?
  • What is the space complexity of your current solution, and can it be optimized if you only needed to return a boolean instead of the count?
  • How would the logic change if each coin could only be used at most once?