CareerCup

Maximum number of $1 bills you can use n1 = x
Maximum number of $2 bills you can use n2 = x/2
Maximum number of $5 bills you can use n5 = x/5
Maximum number of $10 bills you can use n10 = x/10

Create a set A = { n1 times 1, n2 times 2, n5 times 5, n10 times 10 }
Now the problem reduces to finding number of subsets of A whose sum is exactly x, which is the subset sum problem solvable by dynamic programming.

Other than dynamic programming this simple approach works too.

void printAll(SortedList dsortedList, int x)
{
	int sum = 0;
	int highest = INT_MAX;
	Set set = new Set();	//	Use  hash.
	do{
		highest = findLessThan(dsortedList, highest);
		// findLessThan returns element of the list that is less than highest.
		
		if(highest == NULL)		//	No more elements left.
			break;		
		sum = sum + highest;
		if(sum <= x)
			set.add(highest);
		else if(sum == x)
			print(soFar);
			removeAll(dsortedList, set);
			set.clear();
			sum = 0;
		else 
			sum = sum-highest
				 
		
	}while(true)
	
	
}

Here is a geeksforgeeks solution:-)

.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

public static void main(String[] args)
{
int[] coins={1,4,6,2,3,5};
int count=0;


for (int i=0;i<coins.length;i++)
{
count=count+Count(9,coins,i,0);
}
System.out.println(count);
}

public static int Count(int Sum,int[] coins,int index,int curSum)
{
int count=0;

if (index>=coins.length)
return 0;

int sumNow=curSum+coins[index];
if (sumNow>Sum)
return 0;
if (sumNow==Sum)
return 1;

for (int i= index+1;i<coins.length;i++)
count+=Count(Sum,coins,i,sumNow);

return count;

}

int GetConbimationCount(int n)
{
	if(n <= 0)
		return 0;

	int[] baseCount = new int[](10);
	baseCount[0] = 1;

	for(int i = 1; i < 10 || i < n; i++)
	{
		int count1 = i - 1 > 0 ? baseCount[i - 1] : 0;
		int count2 = i - 2 > 0 ? baseCount[i - 2] + baseCount[2 - 1] : 0;
		int count5 = i - 5 > 0 ? baseCount[i - 5] + baseCount[5 - 1] : 0;
		int count10 = i - 10 > 0 ? baseCount[i - 10] + baseCount[10 - 1] : 0;

		baseCount[i - 1] = Max(count1, count2, count5, count10);
	}
	
	if(x <= 10)
		return baseCount[x - 1];

	int baseCount2 = baseCount[2 - 1];
	int baseCount5 = baseCount[5 - 1];
	int baseCount10 = baseCount[10 - 1];

	or(int i = 11; i <= n; i++)
	{
		int count1 = baseCount[(i - 1) % 10 - 1];
		int count2 = baseCount[(i - 1) % 10 - 2] + baseCount2;
		int count5 = baseCount[(i - 1) % 10 - 5] + baseCount5;
		int count10 = baseCount[(i - 1) % 10 - 10] + baseCount10;

		baseCount[(i - 1) % 10] = Max(count1, count2, count5, count10);
	}

	return baseCount[(n - 1) % 10];
}

int Max(params int[] arr)
{
	int max = arr[0];

	for(int i = 1; i < arr.Length; i++)
	{
		if(arr[i] > max)
			max = arr[i];
	}

	return max;
}

So, here I go.
base cases : countWays(1)=1; countWays(2)=2;countWays(3)=2;countWays(4)=3;countWays(5)=3

Calculate Maximum number of 1,2,5,10 bills that can be used in amount x.
ONES = x; TWOS = x/2; FIVES = x/5; TENS = x/10;
So, number of ways are following. ways = 0;
1. All 1$ bills used. ways+=1;
2. All 2$ bills are used (even amount) or All 2$ and one 1$ bill used (odd amount). ways+=1;
3. (TWOS-1) can be replaced with two 1$ bill. ways+=(TWOS-1)
4. All 5$ bills possible are used and calculate ways of remainder. So, ways+=countWays(n%FIVES).
5. (FIVES-1) bills replaced by 2,2,1$ bills. So, ways+=(FIVES-1)*countWays(n%FIVES)
6. All 10% bills possible are used and calculate ways of remainder. ways+=countWays(n%TENS).
7. (TENS-1) bills replaced by 5,5$ bills. So, ways+=(TENS-1)*ways(n%TENS)

So, here I go.
base cases : countWays(1)=1; countWays(2)=2;countWays(3)=2;countWays(4)=3;countWays(5)=3

Calculate Maximum number of 1,2,5,10 bills that can be used in amount x.
ONES = x; TWOS = x/2; FIVES = x/5; TENS = x/10;
So, number of ways are following. ways = 0;
1. All 1$ bills used. ways+=1;
2. All 2$ bills are used (even amount) or All 2$ and one 1$ bill used (odd amount). ways+=1;
3. (TWOS-1) can be replaced with two 1$ bill. ways+=(TWOS-1)
4. All 5$ bills possible are used and calculate ways of remainder. So, ways+=countWays(n%FIVES).
5. (FIVES-1) bills replaced by 2,2,1$ bills. So, ways+=(FIVES-1)*countWays(n%FIVES)
6. All 10% bills possible are used and calculate ways of remainder. ways+=countWays(n%TENS).
7. (TENS-1) bills replaced by 5,5$ bills. So, ways+=(TENS-1)*ways(n%TENS)

count10=count5=count2=count1=0;
while(x>10)
{
x=x-10;count10++;
}
while(x>5)
{
x=x-5;count5++;
}
while(x>2)
{
x=x-2;count2++;
}
while(x>1)
{
x=x-1;count1++;
}
printf("no of 1s=%d\n no of 5s=%d\n no of 2s=%d,no of1s=%d",count10,count5,count2,count1);


is dis code ok ven ders no limit over no of coins?

Here is the code in Java. Tested with basic use cases. Please let me know if there are any bugs in this.

public static void  findAllCombinationsOfDenominationsWhichAddsToX(int a[], int X){
		findAllCombinationsOfDenominationsUtil(a, X, 0, 0, "");
	}

	public static void findAllCombinationsOfDenominationsUtil(int a[], 
			int X, 
			int current_index,
			int current_sum,
			String resultant_string ){
		for(int i= current_index; i<a.length;i++ ){
			if(current_sum+ a[i] == X){
				//resultant_string = resultant_string + " , " + a[i];
				System.out.println("These denominations can form the sum:"+ 
						resultant_string + "  "+a[i]);
				return;
			}
			else if(current_sum + a[i] < X){

				findAllCombinationsOfDenominationsUtil(a, X, 
						i+1, current_sum + a[i], resultant_string + "  " + a[i]);
			}
		}
	}

Its super simple..

// if coins can repeated

dp[0];
       for (int i=0; i < N; i++)
              for (int j=a[i]; j <= W; j++)
                          dp[j] += dp[j-a[i]];
       return dp[W];

// if coins can be used only once

dp[0] = 1;
      for (int i=0; i < N; i++)
          for (j=W; j>=a[i]; j--)
                    dp[j] += dp[j-a[i]];
      return dp[W];

X = amount to get denominations
n = array size

int count(int X, int n)
{
	if (X == 0) 
		return 1;
	if (X < 0)
		return 0;
	if (n<= 0 && X >= 1)
		return 0;

	return (count(X, n-1) + count(X - a[n-1], n));
}