Pages

Monday, September 7, 2015

Count Posibble Coin Changing Problem (Recursive)

Problem Statement

How many different ways can you make change for an amount, given a list of coins? In this problem, your code will need to efficiently compute the answer.

Task

Write a program that, given

An amount N and types of infinite available coins M
A list of M coins - C={C1,C2,C3,..,CM}

The problem can be formally stated:
Given a value N, if we want to make change for N cents, and we have infinite supply of each of C={C1,C2,…,CM} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

Input : first line is the amount and the second line is the list of distinct coins
Output: Total of combination to get the amount

Input
21
1 2 5 10 20 50 100

Output
44



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Scanner;
public class HelloWorld{

    public static void main(String []args){
        int [] sets = new int[]{1,2,5,10,20,50,100};
        int amount = 21;
        System.out.println(findCount(amount,sets,0));
    }

    public static int findCount(int amount, int coins[], int Index) {
        if (amount == 0)
            return 1;
        else if (amount < 0 || coins.length ==Index)
            return 0;
        else {
            int firstCoin = findCount(amount-coins[Index], coins, Index);
            int nextCoin = findCount(amount, coins, Index+1);
            return firstCoin + nextCoin;
        }
    }
}

No comments:

Post a Comment