CareerCup

A recursive solution.

#include <iostream>
#include <vector>
#include <cstdlib>

using namespace std;

int count(vector<int>& coins, int i, int sum) {
    if (sum == 0) {
        return 1;
    }

    if (sum < 0) {
        return 0;
    }

    if (i <= 0 && 0 < sum) {
        return 0;
    }

    return count(coins, i-1, sum) + count(coins, i, sum-coins[i-1]);
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        cout << argv[0] << " <sum>" << endl;
        exit(0);
    }

    int sum = atoi(argv[1]);

    int c[] = {1,2,3};
    int size = sizeof(c)/sizeof(c[0]);
    vector<int> coins(c, c+size);

    cout << count(coins, size, sum) << endl;
}

For 5 the total combinations without duplicates is 8 and for 4 it is 5
Here is the code using dynamic programming

#include<stdio.h>
#include<stdlib.h>
int noOfDenominations(int *dp,int *denom,int value,int length1)
{
   if(value==0)
   return 0;
   if(value<0)
   return 0;
if(dp[value]!=0)
return dp[value];
  int i;
 for(i=0;i<length1;i++)
{
 
 int diff=value-denom[i];
if(diff==0)
dp[value]=dp[value]+1;
else if((value-denom[i])>=denom[i])
dp[value]=dp[value]+noOfDenominations(dp,denom,value-denom[i],length1);
}
return dp[value];


}
int main()
{


int value=4;
int denominations[]={1,2,3};
int *dp=(int *)calloc(value+1,sizeof(int));
printf("%d",noOfDenominations(dp,denominations,value,3));
  




}

public static void main(String[] args) {
		final int[] coins = new int[] { 1, 2,3 };
		System.out.println(" Combinations :" + getCoinCombinations(0, coins, 5));
	}

	static int getCoinCombinations(final int start, final int[] coins,
			int amount) {
		int result = 0;
		if (amount == 0) {
			return 1;
		}
		for (int i = start; i < coins.length; i++) {
			if (amount >= coins[i]) {
				result += getCoinCombinations(i, coins, amount - coins[i]);
			}
		}
		return result;
	}

public static int findPossibleWays(int val , int [] denominations){
		int []  dp = new int [val+1];
		dp[0] = 0;
	    for (int i =1; i<=val ;++i){
	    	for (int j =0 ;j<denominations.length ;++j){
	    		if (i>=denominations[j]){
	    			dp [i] =dp[i]>dp[i-denominations[j]]+1?dp[i]:dp[i-denominations[j]]+1;
	    		}
	    	}
	    }
	    return dp[val];

}

Assuming denominations have single digit numbers for the convenience of printing -

#include<stdio.h>
#include<stdint.h>
#include<string.h>
#include<stdlib.h>

#define STR_SIZE 35;
#define ndenoms 3

char* appendStr(char *str,char c)
{
int l;
char* pstr = NULL;
l=strlen(str);

pstr = (char*)malloc(35*sizeof(char));
strcpy(pstr,str);
pstr[l]=c;
pstr[l+1]='\0';

return pstr;

}


void findAllpossibleWays(int lastInt, int amt, int *denom,int demonlen ,char* str)
{
int l,i,num;
char* pstr=NULL;

if(amt<=0){

if(amt==0)
{
	printf("%s success \n", str);
}
else
{
	printf("FAIL");
}

return;
}
else
{

for(i=0;i<demonlen;i++)
{
	num = denom[i];
	
	if(amt>=num && lastInt<=num)
	{
		pstr=appendStr(str,num+48); 	
		//printf("%d,",num);
		findAllpossibleWays(num,amt-num,denom, demonlen, pstr);
		free(pstr);
	}		

}
}

}


int main()
{
int amount = 5;

int denom[ndenoms]={1,2,3};
char str[1]= "\0";

findAllpossibleWays(0,amount,denim,ndenoms,str);

}

for convenience i took denominations as boolean array

Split(int amount, bool[] denominations){
  int[,] dp = new int[amount + 1, denominations.Length];
  for (int i = 0; i < denominations.Length; i++)
    dp[0, i] = 1;
  for (int i = 1; i <= amount; i++)
    for (int j = 1; j < denominations.Length; j++){
      dp[i, j] = dp[i, j - 1];
      if (denominations[j] && i>=j)
        dp[i, j] += dp[i - j, j];
    }
  return dp[amount, denominations.Length-1];
}

greedy or dynamic is optimal in this such kind of problems

The question says find all possible ways, and not the number.

Here is non-optimal recursive, generational python code. Dynamic programming can be used to generated all the combinations too.

def combinations(N, coins):
    if len(coins) == 1:
        if N % coins[0] != 0:
            return
        else:
            yield [coins[0]]*(N/coins[0])
        return
   
    if N < 0:
        return
   
    for s in combinations(N, coins[1:]):
        yield s
   
    for s in combinations(N-coins[0], coins):
        yield [coins[0]] + s

#include <vector>
#include <iostream>
using namespace std;

int FindCombination(int amount, const vector<int>& domination, int max_dom_index, vector<int>* combination) {
    if (amount == 0) {
        int comb_size = combination->size();
        if (comb_size == 0)  // if original amount is 0, the combination count may be zero or infinite big number, which depends on your definition.
           return 0;

        // find a combination, output the combination.
        for (int i = 0; i < comb_size-1; ++i) {
            cout << (*combination)[i] << ",";
        }   
        cout << (*combination)[comb_size-1] << endl;
        return 1;
    }   
    int ret = 0;
    // backtracking by trying domination in descending order, thus eliminates duplications. 
    for (int i = max_dom_index; i >= 0; --i) {
        if (amount >= domination[i]) {
             combination->push_back(domination[i]);
             ret += FindCombination(amount-domination[i], domination, i, combination);
             combination->pop_back();
        }   
    }   
    return ret;
}

int FindAllCombinations(int amount, const vector<int>& domination) {
    if (domination.size() == 0)
        return 0;
    vector<int> combination;
    return FindCombination(amount, domination, static_cast<int>(domination.size())-1, &combination);
}

int main (){ 
  vector<int> dom; // assuming dominations have already been sorted.
  dom.push_back(1);
  dom.push_back(2);
  dom.push_back(3);
  int num = FindAllCombinations(7, dom);
  cout << "====================================" << endl;
  cout << "There are " << num << " combinations." << endl;
  return 0;
}

#include <iostream>
using namespace std;

int findWay(int amount, int den[], int maxDen)
{
	if (maxDen == 0)	return 1;
	int sum = 0;
	for (int i = amount/den[maxDen]; i>=0; i--)
		sum += findWay(amount-(i*den[maxDen]), den, maxDen-1);
	return sum;
}

int main() {
	int myDen[3] = {1, 2, 3};	
	cout<<"There are "<<findWay(5, myDen, 2)<<" ways."<<endl;
	return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;


public class DenominationsOfCoins {
	
	Set<Integer> mAllowedDenominations;
	DenominationsOfCoins(){
		mAllowedDenominations = new TreeSet<Integer>();
		mAllowedDenominations.add(1);
		mAllowedDenominations.add(2);
		mAllowedDenominations.add(3);
	}

	public static void main(String[] args){
		DenominationsOfCoins obj = new DenominationsOfCoins();
		obj.findPossibleCombiations(5);
	}
	
	int findPossibleCombiations(int num){
		List<String> possibilities = doFindPossibleCombiations(num, 0);
		for(String str:possibilities){
			System.out.println(str);
		}
		return possibilities.size();
	}
	
	List<String> doFindPossibleCombiations(int num, int sumWith){
		List<String> possibilities = new ArrayList<String>();
		for(int denom:mAllowedDenominations){
			if(denom > num){
				break;
			}
			if(denom < sumWith){
				continue;
			}
			int remainder = num - denom;
			if(remainder==0){
				possibilities.add(String.format("%d", denom));
				break;
			} else if(remainder >= denom){
				List<String> possibilitiesWithRemainder = doFindPossibleCombiations(remainder, denom);
				for(String str:possibilitiesWithRemainder){
					possibilities.add(String.format("%d, %s", denom, str));
				}
			}
		}
		return possibilities;
	}

}

DFS

enum{ONE=1,TWO,THREE};
void find_path(int remain, int type, vector<int>&res)
{
if(remain < type)
return;

if(remain-type == 0)
{
	//found one solution print
       for(size_t i = 0; i < res.size();i++)
        {
            cout<<res[i]<<" ";
        }
          cout<<type<<endl;
         return ;
    }
    res.push_back(type);
    for(int i=1;i<=type;i++){find_path(remain-type, i, res);}
    res.pop_back();

}

int main()
{
vector<int> res;
    find_path(5, ONE, res);
    find_path(5, TWO, res);
    find_path(5, THREE, res);
}

This code is in java. Logic is simple, using recursion.

public void printAllDenom(final List<Integer> numbers, int sum, List<Integer> result, int index)
 {
      if (sum < 0) return;
      if (index > numbers.size() - 1) return;
      if (sum == 0) 
      {
        System.out.println(result); // When sum is 0, we have one solution in result list.
        return;
      }
      
      if (numbers.get(index) != -1)
      {
        printAllDenom(numbers, sum, result, index + 1);
        result.add(numbers.get(index));
        printAllDenom(numbers, sum - numbers.get(index), result, index);
        result.remove(result.size() - 1);
      }
  }

#procedure for generating subsets 
out = []   
def subset(s,i,ss) :
 global out
 if i == len(s):
    return
 else :
    ss.append(s[i])
    out.append(list(ss))
    i = i+1
    subset(s,i,ss)
    ss.pop()
    subset(s,i,ss)

#intialising variables
s = []
ss = []
target = 5
denom = [1,2,3]

#generate the list [1,1,1,1,1,2,2,3]
for var in denom :
  fac = target / var
  for i in range(0,fac) :
    s.append(var)

#generate the all subsets of list [1,1,1,1,1,2,2,3]
subset(s,i,ss)

#remove duplicate lists in the above generated subsets
out = set(tuple(x) for x in out)
out = [list(x) for x in out]

#increment the count if the sum of the subset is 5 
cnt = 0
for x in out :
  if sum(x) == target :
    cnt = cnt + 1
    
print cnt

import math
def findAllDenomination(val, allDenominations):
  possibleDenominations = []
  if val == 0:
    return possibleDenominations
  tempDenominations = allDenominations.copy();
  theDenomination = tempDenominations.pop();
  highestDenominations = math.trunc(val/theDenomination);
  if len(tempDenominations) == 0:
    if val%theDenomination == 0:
      currentDenominations = []; 
      for i in range(0, highestDenominations):
        currentDenominations.append(theDenomination);
      possibleDenominations.append(currentDenominations);
  else:
    for i in range(0, highestDenominations+1):
      if (val - theDenomination*i) == 0:
        currentDenominations = [];
        for j in range(0, i):
          currentDenominations.append(theDenomination);
        possibleDenominations.append(currentDenominations);
      else:
        allPossibleLowerDenominations = findAllDenomination(val - theDenomination*i, tempDenominations)
        if len(allPossibleLowerDenominations) != 0:
          currentDenominations = []; 
          for j in range(0, i):
            currentDenominations.append(theDenomination);
          for lowerPossDenominations in allPossibleLowerDenominations:
            lowerPossDenominations.extend(currentDenominations);
            possibleDenominations.append(lowerPossDenominations);
  return possibleDenominations 

possDenominations = findAllDenomination(5, [1,2,3])
print(possDenominations)

int getCount(int[] denom, int value) {
	return getCount(denom, 0, value);
}
int getCount(int[] denom, int index, int reqValue) {
	int value = 0;
	int count = 0;
	if (index == denom.length) {
		return 0;
	}
	while(value < reqValue)
	{
		value += denom[index];
	}
	if (reqValue == value)
		count++;
	value -= denom[index];
	while(value >= 0) {
		count += getCount(denom, index+1, reqValue-value);
		value -= denom[index];
	}
return count;
}

a recursive solution in java.
*assume denom is sorted or we can just sort it

public static void getForms(int n, ArrayList<Integer> denom, int start, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result){
        if(n==0){
            result.add(new ArrayList<Integer>(current));
        }
        else{
            for(int i=start; i<denom.size(); i++){
                if(n>=denom.get(i)){
                    current.add(denom.get(i));
                    getForms(n-denom.get(i), denom, i, current, result);
                    current.remove(current.size()-1);
                }
            }
        }
    }
    
    public static void main(String[] args){
        ArrayList<Integer> denom = new ArrayList<Integer>();
        denom.add(1); denom.add(2); denom.add(3);
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        getForms(5, denom, 0, new ArrayList<Integer>(), result);
        int i=1;

}

//Note denominations should be sorated ascending

class Finder{
int[][] dp; // initialized by -1
int[] denominations;
int find(int amount, int[] denominations){
	this.amount = amount;
	this.denominations = denominations;
	this.dp  = new int[amount][denominations.length]
	for(int i = 0; i < amount; i++){
		for(int j = 0; j < denominations.length; j++){
			dp[i][j] = -1;
		}
}
return _find(amount, 0);
}
private int _find(int amount, int index){ 
	int result = 0;
	if(amount == 0){
		dp[amount][index] = 1;
	return 1;
}else if(amount < 0){
	dp[amount][index] = 0;
	return 0;
}
if(dp[amount][index] != -1){
	return dp[amount][index];
}
for(int i=index;i < denominations.length;i++){
		result += _find(amount-denominations[i], i+1);
}
dp[amount][index] = result;
	return result;
}
}