We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Coin Change II

Number: 518

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Amazon, Morgan Stanley, Zoho, DE Shaw, TikTok, Meta, Uber, Apple, Walmart Labs

Problem Description

Given an integer array of coin denominations and a target amount, determine the number of combinations that sum to the given amount. Each coin can be used infinitely many times, and the order of coins does not matter. Return 0 if the amount cannot be reached with any combination.

Key Insights

  • Use dynamic programming to build up the number of ways to form every amount up to the target.
  • A one-dimensional dp array suffices, where dp[j] represents the number of ways to form sum j.
  • When processing each coin, iterate over amounts from the coin value to the target, updating dp.
  • Order of iteration ensures that combinations, not permutations, are counted.

Space and Time Complexity

Time Complexity: O(n * amount), where n is the number of coins. Space Complexity: O(amount), due to the dp array used for computations.

Solution

We solve the problem by using dynamic programming with a one-dimensional dp array. The dp array is sized as amount + 1 with dp[0] initialized to 1, representing the single way to achieve the amount of 0 (by choosing no coins). For each coin in the coins array, we update every dp[j] for j from the coin’s value up to the target amount: dp[j] is increased by dp[j - coin]. This ensures we consider each coin only once per combination, hence avoiding duplicate counts of the same combination in different orders.

Code Solutions

# Python solution for Coin Change II
def change(amount, coins):
    # Initialize dp array where dp[j] represents the number of ways to form amount j
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to achieve amount 0 (use no coins)
    
    # Process each coin
    for coin in coins:
        # Update dp for all amounts from coin to target amount
        for j in range(coin, amount + 1):
            dp[j] += dp[j - coin]  # Accumulate ways by using coin
    return dp[amount]

# Example usage:
print(change(5, [1, 2, 5]))  # Output: 4
← Back to All Questions