CodingGyan

Coin Change: Number of Ways

medium Data Structures and Algorithms

Problem

You have coins of given values (any number of each). Count in how many different ways you can make the amount. The order of coins does not matter (1+2 and 2+1 are the same way). Input: the coins on the first lines and the amount k.

Constraints

  • 1 <= coins <= 100
  • 0 <= amount <= 10^4
  • answer fits in long

Examples

Input

3
1 2 5
5

Output

4

Solutions

Best approachTime O(n k)Space O(k)

Process the coin values one by one. After coin c is processed, ways[v] counts the ways that use only the coins seen so far. The coin loop is outside, so 1+2 and 2+1 are not counted twice.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Count the ways.
 * Input   : Coins and amount.
 * Output  : Number of ways.
 * Approach: 1D table
 * Time    : O(n k)
 * Space   : O(k)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(int[] a, int k) {
        // Step 1: ways[v] is the number of ways to make the value v. There is one way to make 0: no coins.
        long[] ways = new long[k + 1];
        ways[0] = 1;
        // Step 2: Use one coin value at a time. Going over the coins in the outer loop counts each set of coins once.
        for (int coin : a) {
            for (int v = coin; v <= k; v++) {
                ways[v] += ways[v - coin];
            }
        }
        return ways[k];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        int k = scanner.nextInt();
        System.out.println(solve(a, k));
    }
}
Hints (2)
  1. Why is the coin loop the outer loop?
  2. What is ways[0]?

Try these next