CareerCup

Please check this one - looks like works

#include <iostream>
#include <vector>

void printAllCoinsCombinationComplex(int Sum, std::vector<int>& denominations, std::vector<int> coinsValue, int currentCoinIndex, int maxCoinsNumber)
{
    if (Sum == 0 && maxCoinsNumber == 0)
    {
        //result
        for (size_t i = 0; i < denominations.size(); ++i)
        {
            for (int j = coinsValue[i]; 0 < j; --j)
            {
                std::cout <<  denominations[i] << " " ;
            }
        }
        std::cout << std::endl;
        return;
    }
    
    if (Sum == 0 || maxCoinsNumber == 0)
    {
        //no valid combinations 
        return;
    }

    if (currentCoinIndex >= denominations.size())
        return;

    for (int i = 1; i*denominations[currentCoinIndex] <= Sum; ++i)
    {
        coinsValue[currentCoinIndex] +=i;
        printAllCoinsCombinationComplex(Sum - i*denominations[currentCoinIndex], denominations, coinsValue, currentCoinIndex+1, maxCoinsNumber-coinsValue[currentCoinIndex]);
        coinsValue[currentCoinIndex] -=i;
    }

    if (currentCoinIndex+1 < denominations.size())
        printAllCoinsCombinationComplex(Sum, denominations, coinsValue, currentCoinIndex+1, maxCoinsNumber);
}

int main()
{
    int denominations[] = {25, 10, 5, 1};
    std::vector<int> vDenominations(&denominations[0], &denominations[(sizeof denominations / sizeof(int)) ]);
    std::vector<int> vValues(vDenominations.size(), 0);
    printAllCoinsCombinationComplex(30, vDenominations, vValues, 0, 6);
    return 0;
}

its a DP problem, similar to coin change problem, only change is that denomination should not be repeated..

I think as per the problem the denominations could be repeated. As I understand it first solve for the coin change problem that sum up to the change value n. then print out the different combinations (non-repeated) of the denominations that were used to sum up to n.

this problem turned out to be much easier to solve than using dp. There is the polynomial solution with the recursive calls + some logic to cut off the calls that lead to the already inspected combinations.

public static void main(String[] args) {
		
		int aSum = 26;
		int[] denom = {25, 10, 5, 1};
		
		findValidCombos(denom, aSum, denom.length, 0, new ArrayList<Integer>(),    validCombos );
		for(List<Integer> combo: validCombos) {
			for(int i = 0 ; i < combo.size(); i++)
				System.out.print(denom[i] +" X "+ combo.get(i) +"\t");
			System.out.println();
		}		
	}

	private static void findValidCombos(int[] denom,int aSum,  int maxlevel, int level, List<Integer> stack, List<List<Integer>> validCombo ) {
		int d = denom[level];
		for(int i = aSum/d ; i >=0 ; i--) {
			int a = d * i;
			stack.add(i);
			if(maxlevel == level+1) {
				//check the sum of combo
				int tSum = 0;
				for(int j = 0 ; j < stack.size(); j++) {
					int x = stack.get(j) * denom[j];
					tSum+=x;
				}
				if(tSum == aSum) {
					//System.out.println(stack);
					List<Integer> combo = new ArrayList<Integer>(stack.size());
					combo.addAll(stack);
					validCombo.add(combo);
				}
				
				stack.remove(stack.size()-1);
			}
			else { 
				findValidCombos(denom, aSum,maxlevel, level+1, stack, validCombo);
				stack.remove(stack.size()-1);
			}
			
			
		}
	}

int a = d * i; - is not used,
denom[j]; - thorws index out of range exception.
Somethign is wrong with this.

Treat this like an odometer problem. Start with zero of each coin. Increment pennies. If pennies takes you past n, then zero pennies and increment nickels. If nickels take you past n, then zero pennies and nickels and increment dimes. If dimes take you past n, then zero pennies/nickels/dimes and increment quarters. If quarters take you past n, then you're done. Each roll of the odometer starts on pennies again.

Once you get a basic odometer working, refine the increment step to be more aggressive. For example, if you are looking at nickels and you're 15 short, jump right ahead to incrementing 3 nickels. If you're 14 short, jump right ahead to two more nickels, and then continue the loop to get more pennies.

dp[i][n][sum]=dp[i-1][n-1][sum-a[i]]+dp[i-1][n][sum]

void printsubset(int a[],int n)
{ for(int i=0;i<n;i++) cout<<a[i]<<" ";
cout<<"\n";
}
void printallsubset(int arr[],int tmp[],int asize,int tsize,int sum,int ite,int targetsum)
{
if(sum==targetsum) {
printsubset(tmp,tsize);
printallsubset(arr,tmp,asize,tsize-1,sum-arr[ite],ite+1,targetsum);
return;
}
else
{ for(int i=ite,i<asize,i++)
{ tmp[tsize]=arr[i];
printallsubset(arr,tmp,asize,tsize+1,sum+arr[i],i+1,targetsum);
}
}
}

def denom_nonrep(l, n, s):
  def denom_int(d, n, s, p):
    if n==0 and s==0:
      print p
      return

    k=[x for x in d if d[x]]
    for x in k:
      d[x]=False
      tmp_s=s
      tmp_n=n
      while(True):
        p.append(x)
        tmp_s-=x
        tmp_n-=1
        if (tmp_s<0 or tmp_n<0):
          break
        denom_int(d, tmp_n, tmp_s, p)
      while(tmp_n<n):
        tmp_n+=1
        p.pop()
    for x in k:
      d[x]=True

  d=dict([(x,True) for x in l])
  denom_int(d, n, s, [])

def main():
  l=[1,5,10,25]
  n=6
  s=30
  denom_nonrep(l,n,s)

Implementation in C++ using lambda

#include <stdio.h>

#include <future>
#include <iostream>
#include <algorithm>
#include <type_traits>
#include <vector>

/**
 * input: 
 * sum - the integer amount 
 * n - the number of coins 
 * d - the array contains the coins denominations 
 *
 * WAP that prints all the possible non-repeated combinations of n coins of denominations from d that sum up to n. 
 *
 * Sample of input: 
 * d={1,5,10,25} 
 * sum = 30 
 * n = 6 
 * The expected output: 
 * 1,1,1,1,1,25 
 * 5,5,5,5,5,5
 *
 */
static void
printArray(const std::vector<int> &d, int sum, size_t n)
{
  int result[n];
  std::function<void (int, int, size_t)> rec = [&result, &d, &n, &rec](int lastNumber, int sum, size_t resultSize) {

    if (resultSize) {
      for (size_t i = 0; i < d.size(); ++i) {
        if (sum - d[i] < 0 || d[i] < lastNumber) continue;
        result[n - resultSize] = d[i];
        rec(d[i], sum - d[i], resultSize - 1);
      }
    }
    else if (!sum) {
      for (size_t i = 0; i < n; ++i) {
        std::cout << result[i];
        if (i < n - 1) std::cout << " ";
      }
      std::cout << std::endl;
    }
  };

  rec(0, sum, n);
}

int main(int, char **)
{
  std::vector<int> d = { 1, 5, 10, 25 };

  printArray(d, 30, 6);

  return 0;
}

Could anyone explain the question ?

1,1,1,1,1,25 has 8 coins in it, not n.