Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Coin Change (Number of Ways)

Medium · Dynamic Programming · Asked at Amazon, Microsoft, Paytm, Walmart

Count the ways to make the amount using unlimited coins of the given denominations. Order does not matter. Print the answer modulo 10^9 + 7.

Input

First line: n. Second line: n distinct denominations. Third line: amount.

Output

The number of ways modulo 1000000007.

Constraints

Loop over coins in the outer loop so each combination is counted once.

Example 1

Input

3
1 2 5
5

Output

4

Example 2

Input

1
2
3

Output

0

Hints

  1. dp[x] = number of ways to make amount x; dp[0] = 1 (use no coins).
  2. Coins in the OUTER loop: for each coin c, for x from c up, dp[x] += dp[x − c]. Swapping the loops would count 1+2 and 2+1 separately.

Approach

Process coins one at a time. After handling coins c1..ck, dp[x] counts the multisets of those coins that sum to x. Adding coin c with dp[x] += dp[x − c] (x increasing, so c can be reused) extends each way with one more c. Every combination is built in a fixed coin order, so it's counted once. Take mod 10^9 + 7 at every addition.

Complexity: O(n · amount) time · O(amount) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    const long long MOD = 1000000007;
    int n, amount;
    cin >> n;
    vector<int> coins(n);
    for (auto &c : coins) cin >> c;
    cin >> amount;
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;
    for (int c : coins)
        for (int x = c; x <= amount; x++) dp[x] = (dp[x] + dp[x - c]) % MOD;
    cout << dp[amount] << "\n";
    return 0;
}

Python solution

import sys

MOD = 10**9 + 7
data = list(map(int, sys.stdin.read().split()))
n = data[0]
coins, amount = data[1 : n + 1], data[n + 1]
dp = [1] + [0] * amount
for c in coins:
    for x in range(c, amount + 1):
        dp[x] = (dp[x] + dp[x - c]) % MOD
print(dp[amount])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        final long MOD = 1000000007;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < n; i++) coins[i] = sc.nextInt();
        int amount = sc.nextInt();
        long[] dp = new long[amount + 1];
        dp[0] = 1;
        for (int c : coins)
            for (int x = c; x <= amount; x++) dp[x] = (dp[x] + dp[x - c]) % MOD;
        System.out.println(dp[amount]);
    }
}

Solve Coin Change (Number of Ways) online · All practice problems