CareerCup

Assumption: All the coins have different values. If we have coins with same value then we will start getting duplicate results.

To me this problem looks like finding the combination of the coins and checking if that combination's total is the value we want to compute. So I can extend the find combinations algorithm to do this.

Here is a recursive solution:

public class Change {

	public static int makeChange(int[] coins, int change, int start) {

		int numWays = 0;
		for (int i = start; i < coins.length; i++) {

			if (change - coins[i] == 0) {
				numWays++;
				continue;
			}

			if (i < coins.length) {
				numWays+= makeChange(coins, change - coins[i], i + 1);
			}
		}

		return numWays;

	}

	public static void main(String[] args) {
		int[] input = new int[]{1,2,3,4};
		System.out.println(Change.makeChange(input, 4, 0));
		
	}
}

int total=0;
#define SIZE(a) sizeof(a)/sizeof(a[0])
int arr[] = {1, 2, 3};
int visited[100];

void IsSubArray(int n, int N, int sum) // N is the number of elements in the array 
{
        visited[n] = 1;
        if(sum == N) {
                total++;
                visited[n] = 0;
                return;
        }

        if((n <= (SIZE(arr)-1)) && arr[n]+sum <= N) {
                IsSubArray(n+1, N, sum+arr[n]);
        }

        if((n <= (SIZE(arr)-1)) && arr[n+1]+sum <= N) {
                visited[n] = 0;
                IsSubArray(n+1, N, sum);
        }
}

int main()
{
        int j, i;
        int target_sum=3;

        memset(visited, 0, sizeof(int)*100);
        IsSubArray(0, target_sum, 0);
        printf("total %d\n", total);
        return 0;
}

If coins are 1,2,3,4 and amount is 4 then possible set is {4}.
if amount is 3 then {1,2} and {3} are possible.
So max two set are possible. min one set is also possible.
If the amount is power of 2 then only one set is possible else two sets are possible.

If we take binary form of that given number then easily we can solve this problem

- we have n coins each of unique denomination
- a coin once selected cannot be reused/repeated (sampling without replacement)
- number of subsets of a set of n coins = 2^n
- brute force: compare sum of elements in a subset with the desired amount.
- Repeat 2^n times - obviously bad. Exponential time complexity
- So, sort the set. Use binary search to find the desired denomination
- The denomination is either present in the set, or not.
- Either way, you will know the coins lesser than A. Reject all coins bigger than A.
- Apply the brute algorithm (above) to this list of subsets (having coins smaller than A).
- This way, at least we reduce the time complexity to half (but it remains exponential)

Sort all the denominations in increasing order and let Di denotes ith denomination.
Let N(i,K) = Number of ways of obtaining an amount K only using denominations from D1 to Di.

N(i,K) = Max ( N(i-1,K) , N(i-Di,K-Di) + Di ) 

Optimum solution for K=A is Max of all N(i, A)

This can be easily solved using dynamic programming, Be careful while initializing values.

This should work in O(n^2) time and O(n^2) space.

if we use greedy algorithm, the greedy standard is using the minimum number of coins to form the result.
First, order the coins array by their values, after that, the value will be in non-descending order.
Second, search the array from the largest point.
If the largest value is equal to the 'A', we set the element has been visited;
else if the largest value is less than 'A', we set the element has been visited, and search the elements which can be added to get 'A',
if we should add three or more values to get 'A', we can also use a temp value to replace 'A';
if the largest value is larger than 'A', just ignore it and set the element has been visited.
This method can ensure we use the least number of coins to get 'A'.

void subSum(int M,int arr[],int k,int s,int n, int res[])
{
	if(s+arr[k]==M)
	{
		res[k]=1;
		return;
	}
	if(k+1<n&&(s+arr[k]<=M))
	{
		res[k]=1;
		subSum(M,arr,k+1,s+arr[k],n,res);
	}
	if(k+1<n&&(s+arr[k+1])<=M)
	{
		res[k]=0;
		subSum(M,arr,k+1,s,n,res);
	}
}

import java.util.ArrayList;
import java.util.List;

public class Bag {

public static void main(String[] args)
{
System.out.println("begin");

List<Integer> from = new ArrayList<Integer>();

List<Integer> to = new ArrayList<Integer>();

from.add(1);
from.add(2);
from.add(3);
from.add(4);
from.add(5);
from.add(6);
from.add(7);

fill(from, to,0, 9);

System.out.println("end");
}

private static void fill(List<Integer> from, List<Integer> to, int index, Integer target)
{
if(sum(to) == target)
{
System.out.println(print(to));
return;
}

while (index < from.size()) {

Integer current = from.get(index);

List<Integer> newto = Copy(to);

List<Integer> newfrom = Copy(from);

newto.add(current);

newfrom.remove(current);

fill(newfrom, newto, index, target);

index++;
}
}

private static String print(List<Integer> to) {

String output = "{";

for (int i = 0; i < to.size(); i++) {
output += to.get(i) + ",";
}

return output.subSequence(0, output.length()-1) + "}";
}

private static Integer sum(List<Integer> from) {
Integer sum = 0;

for (int i = 0; i < from.size(); i++) {
sum += from.get(i);
}

return sum;
}

private static List<Integer> Copy(List<Integer> input)
{
ArrayList<Integer> output = new ArrayList<Integer>();

for (int i = 0; i < input.size(); i++) {
output.add(input.get(i));
}
return output;
}

}

#include<stdio.h>
/*
	
	
	
	solution : Dry Run on small input

*/
int makeChange(int a[],int n,int sum)
{
	int i,j,k,l,count=0,M[n+1][sum+1];
	int stk[n],top=-1;
	int q,w;
	int flg=0;
	for(i=0;i<=sum;i++)
		M[0][i] = 0;
	if(a[0] <sum)M[0][a[0]] = 1;
	
	for(i=0;i<=n;i++)
		M[i][0] = 0;
	printf("\n");
		for(q=0;q<=n;q++)
		{
			printf("\n");
			for(w=0;w<=sum;w++)
				printf("%d\t",M[q][w]);
		}
	for(i=1;i<n;i++)
	{

		printf("\n%d\n",i);
		for(j=1;j<=sum;j++)
		{
			M[i][j]= M[i-1][j];
			if(j>=a[i])
			{
				if(M[i-1][j-a[i]] ==1 || j ==a[i])
					M[i][j] = 1;

			}
		}
		q=0;w=0;
		printf("\n");
		for(q=0;q<=n;q++)
		{
			printf("\n");
			for(w=0;w<=sum;w++)
				printf("%d\t",M[q][w]);
		}
		if(M[i][sum]==1)
		{
			M[i][0] = -1;
						top++;
						stk[top]=i;
			k = i-1;
			l = sum-a[i];
			if(l==0){
				M[i][0]=-1;				
			}
			while(M[k][l]==1 && k>=0 && l>0)
			{
				if(M[k-1][l]==1)
				{
					k--;
					continue;
				}
				else
				{

					if(M[k][0]!=0)
					{
						while(top>-1)
						{
							M[stk[top]][0] = 0;
							top--;
						}
						break;

					}
					else
					{
						M[k][0] = -1;
						top++;
						stk[top]=k;
						l = l-a[k];
						k--;				

					}
				}

			}
			if(l==0)
			{
				count++;
				top=-1;
			}
			else
			{
				while(top>-1)
				{
					M[stk[top]][0] = 0;
					top--;
				}
			}

		}		
		
	}

	printf("\n");
		for(q=0;q<=n;q++)
		{
			printf("\n");
			for(w=0;w<=sum;w++)
				printf("%d\t",M[q][w]);
		}
	return count;	

}
void main()
{
	int n,a[500],sum;
	int i,j;
	scanf("%d%d",&n,&sum);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	j=makeChange(a,n,sum);
	printf("\n%d\n",j);
}

use DP
C(i,a) = c(i-1,a) + c(i-1,a-a(i));
c(i,a) = 1 if a is 0;
c(i,a) = 0 if i is zero and a> 0
if whie calculation we found a-a(i) < 0, consider that to zero.