Coding

Coin change II

Asked at

Google

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Give an array coins of n integers representing coin denominations. Your task is to find the number of distinct combinations that sum up to a specified amount of money. If it's impossible to achieve the exact amount with any combination of coins, return 0. Single coin can be used any number of times. Return your answer with modulo 109+7.

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

Output: 4

Explanation: The four combinations are: 10 = 10 10 = 4 + 4 + 2 10 = 4 + 2 + 2 + 2 10 = 2 + 2 + 2 + 2 + 2

Input: coins = [5], amount = 5

Output: 1

Explanation: There is one combination: 5 = 5.

Input: coins = [1, 2, 3, 5], amount = 5

1 <= n, coins[i], amount <= 103
All the values of **coins **are unique.

cpp

class Solution {
  public:
   int count(vector<int>&coins, int N, int amount) {
        
    }
};

java

class Solution {
    public int count(int[] coins, int N, int amount) {
      
    }
}

python

class Solution:
    def count(self, coins, N, amount):

javascript

class Solution {
    count(coins, N, amount) {
     
    }
}

csharp

class Solution
{
    public int count(int[] coins, int N, int amount)
    {
      
    }
}

func count(coins []int, N int, amount int) int {
   
}

Stuck? Show a way to structure it+

01Set dp[0]=1 as the one way to form zero.
02Process coin denominations in the outer loop.
03For each coin, update amounts from coin through target.
04Add dp[amount-coin] into dp[amount], applying modulo if required.

Reference answer

To count combinations independent of order, process coins one at a time. Initialize dp[0]=1. For each coin c, loop amount from c to target and do dp[amount]+=dp[amount-c]. By the time a coin is processed, every way in the array uses only current-or-earlier denominations, so the same set is counted once rather than once per ordering. Increasing amount order intentionally permits unlimited copies of the current coin. Time is O(numberOfCoins * target), space O(target). Use the stated modulus or a wide integer. Reversing the loops counts ordered sequences instead.

Then expect these follow-ups

How would you find the minimum number of coins instead?
Tests: DP variant
How would you count ordered sequences?
Tests: loop-order semantics

Hiring now

Google has 52 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Small Business Field Sales Representative
Denver, Colorado
Senior Technical Program Manager, Special Projects
Denver, Colorado; Lakewood, Colorado, United States
OSP Engineering Lead, Technical Operations
Denver, Colorado

Or practice this question first

Next question