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; } } }