CareerCup

this is the dynamic program for coin denomination problem,

puddleofriddles.blogspot.com/2012/03/you-are-given-n-types-of-coin.html

4+4+5

Simple solution is to use recursion, but it will keep track of the order in which the coins are selected, so for 13 we will have 4,4,5; 4,5,4 and 5,4,4

Code:

using System;
using System.Collections.Generic;

namespace _4_5_7_13
{
    class Program
    {

        public static void printNumbers(List<int> coinDenominations,List<int> numSoFar, int remainder, int originalNumber)
        {
            bool leftCoins = false;
            //any valid combinations left ?
            foreach (int coin in coinDenominations)
            {
                if (coin <= remainder)
                {
                    leftCoins = true;
                    break;
                }
            }

            if (!leftCoins)
            {
                //remainder is less than the minimum coin, can't do anything
            }
            else
            {
                if (coinDenominations.Contains(remainder))
                {
                    numSoFar.Add(remainder);
                    for (int i = 0; i < numSoFar.Count; i++)
                    {
                        Console.Write(numSoFar[i]);
                        if (i == numSoFar.Count - 1)
                        {
                            Console.Write("=");
                        }
                        else
                        {
                            Console.Write("+");
                        }
                    }
                    Console.WriteLine(originalNumber);
                }

                foreach (int coin in coinDenominations)
                {
                    if (remainder >= coin)
                    {
                        List<int> newList = new List<int>(numSoFar);
                        newList.Add(coin);
                        printNumbers(coinDenominations, newList, remainder - coin, originalNumber);
                    }
                }
            }
        }
        static void Main(string[] args)
        {
            int numToSum = 13;
            printNumbers(new List<int>{4, 5, 7}, new List<int>(), numToSum, numToSum);
        }
    }
}

Output:
4+4+5=13
4+5+4=13
5+4+4=13
Press any key to continue . . .

public static int [] set = {7,5,4};
public static ArrayList<Integer> coll = new ArrayList<Integer>();
	
public static void function(int target){
	if(target == 0){
		for(int i : coll){
			System.out.print(i);
		}
		System.out.println("");
		coll.remove(coll.size()-1);
	}
	else{
		for(int i=0; i<set.length; i++){
			if(set[i] <= target){
				coll.add(set[i]);
				target = target-set[i];
				function(target);
				target = target+set[i];
			}
		}
		if(!coll.isEmpty()){
			coll.remove(coll.size()-1);
		}
	}
}
public static void main(String [] args){
	function(13);
}

#include<stdio.h>

#define A 4
#define B 5
#define C 7

int factor(int n, int q){
	if(!n || n<A){
		if(!n) printf("%d, ", q);
		return n;
	}
	if(q) printf("%d, ", q);
	return factor(n-A, A)?factor(n-B, B)?factor(n-C, C)?n:0:0:0;
}

int main(void) {

	int n;
	printf("Enter number ");
	scanf("%d",&n);

	if(!factor(n, 0))
		printf(" Possible\n");	
	else 
		printf(" Not Possible\n");
	return 0;
}

public class FindCoinDenominations {
	public static void main(String[] args) {
		int x=4,y=5,z=7;
		int total =13; //
		int n = total / x +1;
		int val=0;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				for (int k=0;k<n;k++)
				{	val = (k*x) + (j*y) + (i*z);
					if (val==total)
					{
						System.out.println(k+"*"+x+"p,"+j+"*"+y+"p,"+i+"*"+z+"p");
						break;
					}
				}
	}
}
o/p
2*4p,1*5p,0*7p   , when total=13

3*4p,3*5p,0*7p, when total =27
5*4p,0*5p,1*7p
0*4p,4*5p,1*7p
2*4p,1*5p,2*7p