How to find all combinations of coins when given some dollar value

Question

I found a piece of code that I was writing for interview prep few months ago   According to the comment I had  it was trying to solve this problem      Given some dollar value in cents  e g  200   2 dollars  1000   10 dollars   find all the combinations of coins that make up the dollar value    There are only pennies  1     nickels  5     dimes  10     and quarters  25    allowed    For example  if 100 was given  the answer should be   4 quarter s  0 dime s  0 nickel s  0 pennies   3 quarter s  1 dime s  0 nickel s  15 pennies   etc    I believe that this can be solved in both iterative and recursive ways  My recursive solution is quite buggy  and I was wondering how other people would solve this problem  The difficult part of this problem was making it as efficient as possible

User · Answer

I used a really simple loop to solve this in a BlackJack game I'm writing in HTML5 using the Isogenic Game Engine. You can see a video of the BlackJack game which shows the chips that were used to make up a bet from the bet value on the BlackJack table above the cards: http://bit.ly/yUF6iw

In this example, betValue equals the total value that you wish to divide into "coins" or "chips" or whatever.

You can set the chipValues array items to whatever your coins or chips are worth. Make sure that the items are ordered from lowest value to highest value (penny, nickel, dime, quarter).

Here is the JavaScript:

// Set the total that we want to divide into chips
var betValue = 191;

// Set the chip values
var chipValues = [
    1,
    5,
    10,
    25
];

// Work out how many of each chip is required to make up the bet value
var tempBet = betValue;
var tempChips = [];
for (var i = chipValues.length - 1; i >= 0; i--) {
    var chipValue = chipValues[i];
    var divided = Math.floor(tempBet / chipValue);

    if (divided >= 1) {
        tempChips[i] = divided;
        tempBet -= divided * chipValues[i];
    }

    if (tempBet == 0) { break; }
}

// Display the chips and how many of each make up the betValue
for (var i in tempChips) {
    console.log(tempChips[i] + ' of ' + chipValues[i]);
}

You obviously don't need to do the last loop and it is only there to console.log the final array values.

User · Answer

public static int calcCoins int cents           return coins cents new int cents 1              public static int coins int cents int   memo           if memo cents     0               return -1                    int sum   0          int arr      25 10 5 1            for  int i   0  i  lt  arr length  i                  if cents arr i     0                   int temp   coins cents-arr i  memo                   if temp    0                       sum  1                    else if temp    -1                       sum   0                                    else                      sum    temp                                                     memo cents    sum          return sum

User · Answer

In Scala Programming language i would do it like this    def countChange money  Int  coins  List Int    Int             money match              case 0   gt  1            case x if x  lt  0   gt  0            case x if x  gt   1  amp  amp  coins isEmpty   gt  0            case     gt  countChange money  coins tail    countChange money - coins head  coins

User · Answer

I found this neat piece of code in the book  Python For Data Analysis  by O reily  It uses lazy implementation and int comparison and i presume it can be modified for other denominations using decimals  Let me know how it works for you    x000D   x000D  def make change amount  coins  1  5  10  25   hand None   x000D   hand      if hand is None else hand x000D   if amount    0  x000D   yield hand x000D   for coin in coins  x000D     ensures we don t give too much change  and combinations are unique x000D   if coin  gt  amount or  len hand   gt  0 and hand -1   lt  coin   x000D   continue x000D   for result in make change amount - coin  coins coins  x000D   hand hand    coin    x000D   yield result x000D   x000D   x000D

User · Answer

This is my answer in Python  It does not use recursion   def crossprod  list1  list2       output   0     for i in range 0 len list1            output    list1 i  list2 i       return output  def breakit target  coins       coinslimit     target   coins i   for i in range 0 len coins        count   0     temp          for i in range 0 len coins            temp append  j for j in range 0 coinslimit i  1          r          for x in temp          t              for y in x              for i in r                  t append i  y           r   t      for targets in r          if crossprod targets  coins     target              print targets             count   1     return count     if   name         main         coins    25 10 5 1      target   78     print breakit target  coins    Example output              1   10 cents   2   5 cents   58   1 cents        4   5 cents   58   1 cents        1   10 cents   1   5 cents   63   1 cents        3   5 cents   63   1 cents        1   10 cents   68   1 cents        2   5 cents   68   1 cents        1   5 cents   73   1 cents        78   1 cents        Number of solutions    121

User · Answer

The code is using Java to solve this problem and it also works    This method may not be a good idea because of too many loops  but it s really a straight forward way   public class RepresentCents        public static int sum int n             int count   0          for  int i   0  i  lt   n   25  i                  for  int j   0  j  lt   n   10  j                      for  int k   0  k  lt   n   5  k                          for  int l   0  l  lt   n  l                              int v   i   25   j   10   k   5   l                          if  v    n                                count                              else if  v  gt  n                                break                                                                                                    return count             public static void main String   args            System out println sum 100

User · Answer

Straightforward java solution   public static void main String   args             int   denoms    4 2 3 1       int   vals   new int denoms length       int target   6      printCombinations 0  denoms  target  vals       public static void printCombinations int index  int   denom int target  int   vals      if target  0          System out println Arrays toString vals        return        if index    denom length  return       int currDenom   denom index     for int i   0  i currDenom  lt   target i            vals index    i      printCombinations index 1  denom  target - i currDenom  vals       vals index    0

User · Answer

var countChange   function  money coins      function countChangeSub money coins n        if money  0  return 1      if money lt 0    coins length   n  return 0      return countChangeSub money-coins n  coins n    countChangeSub money coins n 1         return countChangeSub money coins 0

User · Answer

make a list of all distinct sets of coins of from the set of coins to   sum up to the given target amount    Here the input set of coins is assumed yo be  1  2  4   this set MUST   have the coins sorted in ascending order    Outline of the algorithm       Keep track of what the current coin is  say ccn  current number of coins   in the partial solution  say k  current sum  say sum  obtained by adding   ccn  sum sofar  say accsum     1  Use ccn as long as it can be added without exceeding the target       a  if current sum equals target  add cc to solution coin set  increase       coin coin in the solution by 1  and print it and return       b  if current sum exceeds target  ccn can t be in the solution  so          return       c  if neither of the above  add current coin to partial solution           increase k by 1  number of coins in partial solution   and recuse    2  When current denomination can no longer be used  start using the       next higher denomination coins  just like in  1     3  When all denominations have been used  we are done      include  lt iostream gt   include  lt cstdlib gt   using namespace std      int num calls   0     int num ways   0   void print const int coins    int n    void combine coins                     const int denoms       coins sorted in ascending order                    int n                  number of denominations                    int target             target sum                    int accsum             accumulated sum                    int coins              solution set  MUST equal                                           target   lowest denom coin                    int k                  number of coins in coins                              int  ccn       current coin     int  sum       current sum           num calls       for  int i   0  i  lt  n    i                          skip coins of lesser denomination  This is to be efficient            and also avoid generating duplicate sequences  What we need            is combinations and without this check we will generate            permutations                      if  k  gt  0  amp  amp  denoms i   lt  coins k - 1               continue       skip coins of lesser denomination          ccn   denoms i            if   sum   accsum   ccn   gt  target              return         no point trying higher denominations now           if  sum    target                   found yet another solution             coins k    ccn              print coins  k   1                    num ways              return                     coins k    ccn          combine coins denoms  n  target  sum  coins  k   1            void print const int coins    int n        int s   0      for  int i   0  i  lt  n    i            cout  lt  lt  coins i   lt  lt               s    coins i             cout  lt  lt    t    t   lt  lt  s  lt  lt    n       int main int argc  const char  argv           int denoms      1  2  4       int dsize   sizeof denoms    sizeof denoms 0        int target       if  argv 1           target   atoi argv 1        else         target   8       int  coins   new int target         combine coins denoms  dsize  target  0  coins  0           cout  lt  lt   num calls      lt  lt  num calls  lt  lt     num ways      lt  lt  num ways  lt  lt    n        return 0

User · Answer

The sub problem is a typical Dynamic Programming problem      Q  Given some dollar value in cents  e g  200   2 dollars  1000   10 dollars         find the number of combinations of coins that make up the dollar value        There are only penny  nickel  dime  and quarter         quarter   25 cents  dime   10 cents  nickel   5 cents  penny   1 cent        A  Reference  http   andrew neitsch ca publications m496pres1 nb pdf f n  k   number of ways of making change for n cents  using only the first          k 1 types of coins              - 0                         n  lt  0    k  lt  0 f n  k     - 1                         n    0            - f n  k-1    f n-C k   k   else       include  lt iostream gt   include  lt vector gt  using namespace std   int C      1  5  10  25       Recursive  very slow  O 2 n  int f int n  int k        if  n  lt  0    k  lt  0          return 0       if  n    0          return 1       return f n  k-1    f n-C k   k          Non-recursive  fast  but still O nk  int f NonRec int n  int k        vector lt vector lt int gt   gt  table n 1  vector lt int gt  k 1  1         for  int i   0  i  lt   n    i                for  int j   0  j  lt   k    j                        if  i  lt  0    j  lt  0     Impossible  for illustration purpose                               table i  j    0                            else if  i    0    j    0     Very Important                               table i  j    1                            else                                  The recursion  Be careful with the vector boundary                 table i  j    table i  j-1                          i  lt  C j    0   table i-C j   j                                       return table n  k      int main         cout  lt  lt  f 100  3   lt  lt        lt  lt  f NonRec 100  3   lt  lt  endl      cout  lt  lt  f 200  3   lt  lt        lt  lt  f NonRec 200  3   lt  lt  endl      cout  lt  lt  f 1000  3   lt  lt        lt  lt  f NonRec 1000  3   lt  lt  endl       return 0

User · Answer

This is the improvement of Zihan s answer  The great deal of unnecessary loops comes when the denomination is just 1 cent   It s intuitive and non-recursive       public static int Ways2PayNCents int n                int numberOfWays 0          int cent  nickel  dime  quarter          for  quarter   0  quarter  lt   n 25  quarter                          for  dime   0  dime  lt   n 10  dime                                  for  nickel   0  nickel  lt   n 5  nickel                                          cent   n -  quarter   25   dime   10   nickel   5                       if  cent  gt   0                                                numberOfWays    1                          Console WriteLine   0   1   2   3    quarter  dime  nickel  cent                                                                                              return numberOfWays

User · Answer

Here is a python based solution that uses recursion as well as memoization resulting in a complexity of O mxn        def get combinations dynamic self  amount  coins  memo       end index   len coins  - 1     memo key   str amount   - gt   str coins      if memo key in memo          return memo memo key      remaining amount   amount     if amount  lt  0          return        if amount    0          return          combinations          if len coins   lt   1          if amount   coins 0     0              combination                  for i in range amount    coins 0                    combination append coins 0               list sort combination              if combination not in combinations                  combinations append combination      else          k   0         while remaining amount  gt   0              sub combinations   self get combinations dynamic remaining amount  coins  end index   memo              for combination in sub combinations                  temp   combination                    for i in range k                       temp append coins end index                   list sort temp                  if temp not in combinations                      combinations append temp              k    1             remaining amount -  coins end index      memo memo key    combinations     return combinations

User · Answer

Lots of variations here but couldn t find a PHP solution for the number of combinations anywhere so I ll add one in           param int  money The total value     param array  coins The coin denominations     param int  sum The countable sum     return int     function getTotalCombinations  money   coins   amp  sum   0     if   money    0       return  sum        else if  empty  coins      money  lt  0       return  sum      else          firstCoin   array pop array reverse  coins          getTotalCombinations  money -  firstCoin   coins   sum    getTotalCombinations  money  array diff  coins    firstCoin     sum         return  sum       totalCombinations   getTotalCombinations  money   coins

User · Answer

Both  iterate through all denominations from high to low  take one of denomination  subtract from requried total  then recurse on remainder  constraining avilable denominations to be equal or lower to current iteration value

User · Answer

This blog entry of mine solves this knapsack like problem for the figures from an XKCD comic  A simple change to the items dict and the exactcost value will yield all solutions for your problem too   If the problem were to find the change that used the least cost  then a naive greedy algorithm that used as much of the highest value coin might well fail for some combinations of coins and target amount  For example if there are coins with values 1  3  and 4  and the target amount is 6 then the greedy algorithm might suggest three coins of value 4  1  and 1 when it is easy to see that you could use two coins each of value 3    Paddy

User · Answer

Below is a python program to find all combinations of money  This is a dynamic programming solution with order n  time  Money is 1 5 10 25  We traverse from row money 1 to row money 25  4 rows   Row money 1 contains the count if we only consider money 1 in calculating the number of combinations   Row money 5 produces each column by taking the count in row money r for the same final money plus the previous 5 count in its own row  current position minus 5    Row money 10 uses row money 5  which contains counts for both 1 5 and adds in the previous 10 count  current position minus 10    Row money 25 uses row money 10  which contains counts for row money 1 5 10 plus the previous 25 count   For example  numbers 1  12    numbers 0  12    numbers 1  7   7   12-5  which results in 3   1   2  numbers 3  12    numbers 2  12    numbers 3  9   -13   12-25  which results in 4   0   4  since -13 is less than 0   def cntMoney num       mSz   len money      numbers     0   1 num  for   in range mSz       for mI in range mSz   numbers mI  0    1     for mI m in enumerate money           for i in range 1 num 1               numbers mI  i    numbers mI  i-m  if i  gt   m else 0             if mI    0  numbers mI  i     numbers mI-1  i          print  m numbers  m numbers mI       return numbers mSz-1  num   money    1 5 10 25      num   12     print  money combinations  num cntMoney num    output        m numbers   1   1  1  1  1  1  1  1  1  1  1  1  1  1     m numbers   5   1  1  1  1  1  2  2  2  2  2  3  3  3     m numbers   10   1  1  1  1  1  2  2  2  2  2  4  4  4     m numbers   25   1  1  1  1  1  2  2  2  2  2  4  4  4     money combinations   12  4

User · Answer

Scala function     def countChange money  Int  coins  List Int    Int      def loop money  Int  lcoins  List Int   count  Int   Int          if there are no more coins or if we run out of money     return 0    if   lcoins isEmpty    money  lt  0  0   else      if  money    0   count   1       if the recursive subtraction leads to 0 money left - a prefect division hence return count  1        else    keep iterating     sum over money and the rest of the coins and money - the first item and the full set of coins left         loop money  lcoins tail count    loop money - lcoins head lcoins  count         val x   loop money  coins  0  Console println x x

User · Answer

Let C i J  the set of combinations of making i cents using the values in the set J   You can define C as that      first J  takes in a deterministic way an element of a set   It turns out a pretty recursive function    and reasonably efficient if you use memoization

User · Answer

Here s a C  function       public static void change int money  List lt int gt  coins  List lt int gt  combination                if money  lt  0    coins Count    0  return          if  money    0                        Console WriteLine  String Join       combination                 return                     List lt int gt  copy   new List lt int gt  coins           copy RemoveAt 0           change money  copy  combination            combination   new List lt int gt  combination    coins 0             change money - coins 0   coins  new List lt int gt  combination            Use it like this   change 100  new List lt int gt     5  10  25   new List lt int gt        It prints    25  25  25  25 10  10  10  10  10  25  25 10  10  10  10  10  10  10  10  10  10 5  10  10  25  25  25 5  10  10  10  10  10  10  10  25 5  5  10  10  10  10  25  25 5  5  10  10  10  10  10  10  10  10  10 5  5  5  10  25  25  25 5  5  5  10  10  10  10  10  10  25 5  5  5  5  10  10  10  25  25 5  5  5  5  10  10  10  10  10  10  10  10 5  5  5  5  5  25  25  25 5  5  5  5  5  10  10  10  10  10  25 5  5  5  5  5  5  10  10  25  25 5  5  5  5  5  5  10  10  10  10  10  10  10 5  5  5  5  5  5  5  10  10  10  10  25 5  5  5  5  5  5  5  5  10  25  25 5  5  5  5  5  5  5  5  10  10  10  10  10  10 5  5  5  5  5  5  5  5  5  10  10  10  25 5  5  5  5  5  5  5  5  5  5  25  25 5  5  5  5  5  5  5  5  5  5  10  10  10  10  10 5  5  5  5  5  5  5  5  5  5  5  10  10  25 5  5  5  5  5  5  5  5  5  5  5  5  10  10  10  10 5  5  5  5  5  5  5  5  5  5  5  5  5  10  25 5  5  5  5  5  5  5  5  5  5  5  5  5  5  10  10  10 5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  25 5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  10  10 5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  10 5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5

User · Answer

Java solution  import java util Arrays  import java util Scanner    public class nCents      public static void main String   args         Scanner input new Scanner System in       int cents input nextInt        int num ways       new int  5  cents 1          putting in zeroes to offset     int getCents    0   0   5   10   25       Arrays fill num ways 0   0       Arrays fill num ways 1   1        int current cent 0      for int i 2 i lt num ways length i              current cent getCents i            for int j 1 j lt num ways 0  length j                 if j-current cent gt  0                   if j-current cent  0                       num ways i  j  num ways i-1  j  1                   else                      num ways i  j  num ways i  j-current cent  num ways i-1  j                                  else                  num ways i  j  num ways i-1  j                                            System out println num ways num ways length-1  num ways 0  length-1

User · Answer

Below is python solution       x          dic          def f n r            a b c d    r         if not dic has key  n a b c d    dic  n a b c d     1         if n gt  25              if not dic has key  n-25 a 1 b c d   f n-25  a 1 b c d               if not dic has key  n-10 a b 1 c d   f n-10  a b 1 c d               if not dic has key  n-5 a b c 1 d   f n-5  a b c 1 d               if not dic has key  n-1 a b c d 1   f n-1  a b c d 1           elif n gt  10              if not dic has key  n-10 a b 1 c d   f n-10  a b 1 c d               if not dic has key  n-5 a b c 1 d   f n-5  a b c 1 d               if not dic has key  n-1 a b c d 1   f n-1  a b c d 1           elif n gt  5              if not dic has key  n-5 a b c 1 d   f n-5  a b c 1 d               if not dic has key  n-1 a b c d 1   f n-1  a b c d 1           elif n gt  1              if not dic has key  n-1 a b c d 1   f n-1  a b c d 1           else              if r not in x                  x extend  r        f 100   0 0 0 0       print x

User · Answer

Duh  I feel stupid right now  Below there is an overly complicated solution  which I ll preserve because it is a solution  after all  A simple solution would be this      Generate a pretty string val coinNames   List   quarter    quarters                            dime    dimes                            nickel    nickels                            penny    pennies    def coinsString      Function tupled  quarters  Int  dimes  Int  nickels Int  pennies  Int    gt        List quarters  dimes  nickels  pennies       zip coinNames    join with names     map  t   gt   if  t  1    1   t  1  t  2  2  else  t  1  t  2  1       correct for number     map  t   gt  t  1         t  2     qty name     mkString           def allCombinations amount  Int       for quarters  lt - 0 to  amount   25        dimes  lt - 0 to   amount - 25 quarters    10        nickels  lt - 0 to   amount - 25 quarters - 10 dimes    5      yield  quarters  dimes  nickels  amount - 25 quarters - 10 dimes - 5 nickels     map coinsString mkString   n    Here is the other solution  This solution is based on the observation that each coin is a multiple of the others  so they can be represented in terms of them       Just to make things a bit more readable  as these routines will access    arrays a lot val coinValues   List 25  10  5  1  val coinNames   List   quarter    quarters                            dime    dimes                            nickel    nickels                            penny    pennies    val List quarter  dime  nickel  penny    coinValues indices toList      Find the combination that uses the least amount of coins def leastCoins amount  Int   Array Int        List amount     coinValues    list  coinValue    gt      val currentAmount   list head     val numberOfCoins   currentAmount   coinValue     val remainingAmount   currentAmount   coinValue     remainingAmount    numberOfCoins    list tail      tail reverse toArray     Helper function  Adjust a certain amount of coins by    adding or subtracting coins of each type  this could    be made to receive a list of adjustments  but for so    few types of coins  it s not worth it  def adjust base  Array Int               quarters  Int              dimes  Int              nickels  Int              pennies  Int   Array Int      Array base quarter    quarters           base dime    dimes           base nickel    nickels           base penny    pennies      We decrease the amount of quarters by one this way def decreaseQuarter base  Array Int    Array Int      adjust base  -1   2   1  0      Dimes are decreased this way def decreaseDime base  Array Int    Array Int      adjust base  0  -1   2  0      And here is how we decrease Nickels def decreaseNickel base  Array Int    Array Int      adjust base  0  0  -1   5      This will help us find the proper decrease function val decrease   Map quarter - gt  decreaseQuarter                       dime - gt  decreaseDime                       nickel - gt  decreaseNickel        Given a base amount of coins of each type  and the type of coin     we ll produce a list of coin amounts for each quantity of that particular    coin type  up to the  base  amount def coinSpan base  Array Int   whichCoin  Int        List base      0 until base whichCoin   toList     list       gt      decrease whichCoin  list head     list         Generate a pretty string def coinsString base  Array Int         base    zip coinNames    join with names   map  t   gt   if  t  1    1   t  1  t  2  2  else  t  1  t  2  1       correct for number   map  t   gt  t  1         t  2    mkString           So  get a base amount  compute a list for all quarters variations of that base     then  for each combination  compute all variations of dimes  and then repeat    for all variations of nickels  def allCombinations amount  Int        val base   leastCoins amount    val allQuarters   coinSpan base  quarter    val allDimes   allQuarters flatMap  base   gt  coinSpan base  dime     val allNickels   allDimes flatMap  base   gt  coinSpan base  nickel     allNickels map coinsString mkString   n      So  for 37 coins  for example   scala gt  println allCombinations 37   0 quarter 0 dimes 0 nickels 37 pennies 0 quarter 0 dimes 1 nickel 32 pennies 0 quarter 0 dimes 2 nickels 27 pennies 0 quarter 0 dimes 3 nickels 22 pennies 0 quarter 0 dimes 4 nickels 17 pennies 0 quarter 0 dimes 5 nickels 12 pennies 0 quarter 0 dimes 6 nickels 7 pennies 0 quarter 0 dimes 7 nickels 2 pennies 0 quarter 1 dime 0 nickels 27 pennies 0 quarter 1 dime 1 nickel 22 pennies 0 quarter 1 dime 2 nickels 17 pennies 0 quarter 1 dime 3 nickels 12 pennies 0 quarter 1 dime 4 nickels 7 pennies 0 quarter 1 dime 5 nickels 2 pennies 0 quarter 2 dimes 0 nickels 17 pennies 0 quarter 2 dimes 1 nickel 12 pennies 0 quarter 2 dimes 2 nickels 7 pennies 0 quarter 2 dimes 3 nickels 2 pennies 0 quarter 3 dimes 0 nickels 7 pennies 0 quarter 3 dimes 1 nickel 2 pennies 1 quarter 0 dimes 0 nickels 12 pennies 1 quarter 0 dimes 1 nickel 7 pennies 1 quarter 0 dimes 2 nickels 2 pennies 1 quarter 1 dime 0 nickels 2 pennies

User · Answer

This is a simple recursive algorithm that takes a bill  then takes a smaller bill recursively until it reaches the sum  it then takes another bill of same denomination  and recurses again  See sample output below for illustration   var bills   new int     100  50  20  10  5  1     void PrintAllWaysToMakeChange int sumSoFar  int minBill  string changeSoFar        for  int i   minBill  i  lt  bills Length  i                  var change   changeSoFar          var sum   sumSoFar           while  sum  gt  0                        if   string IsNullOrEmpty change   change                       change    bills i                sum -  bills i                if  sum  gt  0                                PrintAllWaysToMakeChange sum  i   1  change                                    if  sum    0                        Console WriteLine change                      PrintAllWaysToMakeChange 15  0         Prints the following   10   5 10   1   1   1   1   1 5   1   1   1   1   1   1   1   1   1   1 5   5   1   1   1   1   1 5   5   5 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1

User · Answer

Note  This only shows the number of ways     Scala function   def countChange money  Int  coins  List Int    Int     if  money    0  1   else if  coins isEmpty    money  lt  0  0   else countChange money - coins head  coins    countChange money  coins tail

User · Answer

If the currency system allows it  a simple greedy algorithm that takes as many of each coin as possible  starting with the highest value currency   Otherwise  dynamic programming is required to find an optimal solution quickly since this problem is essentially the knapsack problem   For example  if a currency system has the coins   13  8  1   the greedy solution would make change for 24 as  13  8  1  1  1   but the true optimal solution is  8  8  8   Edit  I thought we were making change optimally  not listing all the ways to make change for a dollar  My recent interview asked how to make change so I jumped ahead before finishing to read the question

User · Answer

Here s some absolutely straightforward C   code to solve the problem which did ask for all the combinations to be shown    include  lt stdio h gt   include  lt stdlib h gt   int main int argc  char  argv          if  argc    2                printf  usage  change amount-in-cents n            return 1             int total   atoi argv 1         printf  quarter tdime tnickle tpenny tto make  d n   total        int combos   0       for  int q   0  q  lt   total   25  q                  int total less q   total - q   25          for  int d   0  d  lt   total less q   10  d                          int total less q d   total less q - d   10              for  int n   0  n  lt   total less q d   5  n                                  int p   total less q d - n   5                  printf   d t d t d t d n   q  d  n  p                   combos                                       printf   d combinations n   combos        return 0      But I m quite intrigued about the sub problem of just calculating the number of combinations   I suspect there s a closed-form equation for it

User · Answer

The below java solution which will print the different combinations as well  Easy to understand  Idea is   for sum 5  The solution is      5 - 5 i  times 1   0         if sum   0             print i times 1     5 - 4 i  times 1   1     5 - 3 times 1   2         2 -  1 j  times 2   0            if sum   0                print i times 1 and j times 2     and so on         If the remaining sum in each loop is lesser than the denomination ie if remaining sum 1 is lesser than 2  then just break the loop  The complete code below  Please correct me in case of any mistakes  public class CoinCombinbationSimple   public static void main String   args        int sum   100000      printCombination sum      static void printCombination int sum        for  int i   sum  i  gt   0  i--            int sumCopy1   sum - i   1          if  sumCopy1    0                System out println i     1 coins                      for  int j   sumCopy1   2  j  gt   0  j--                int sumCopy2   sumCopy1              if  sumCopy2  lt  2                    break                            sumCopy2   sumCopy1 - 2   j              if  sumCopy2    0                    System out println i     1 coins     j     2 coins                               for  int k   sumCopy2   5  k  gt   0  k--                    int sumCopy3   sumCopy2                  if  sumCopy2  lt  5                        break                                    sumCopy3   sumCopy2 - 5   k                  if  sumCopy3    0                        System out println i     1 coins     j     2 coins                                 k     5 coins

User · Answer

This is a really old question  but I came up with a recursive solution in java that seemed smaller than all the others  so here goes -    public static void printAll int ind  int   denom int N int   vals       if N  0           System out println Arrays toString vals            return            if ind     denom length  return                   int currdenom   denom ind       for int i 0 i lt   N currdenom  i             vals ind    i          printAll ind 1 denom N-i currdenom vals              Improvements     public static void printAllCents int ind  int   denom int N int   vals           if N  0               if ind  lt  denom length                    for int i ind i lt denom length i                        vals i    0                            System out println Arrays toString vals                return                    if ind     denom length                 vals ind-1    0              return                                  int currdenom   denom ind           for int i 0 i lt   N currdenom  i                      vals ind    i                  printAllCents ind 1 denom N-i currdenom vals

User · Answer

The following one-liner in Mathematica produces the desired result parts n    Flatten Table   n-i  25  i-j  10  j-k  5 k   i n 0 -25   j i 0 -10   k j 0 -5   2   The table trivially builds up all combinations by iterating through all ways of how many coins of a bigger kind fit into n  while repeating the same steps with coins of smaller kind for the remainder  The implementation should be similarly trivial in any other programming language  The output is a list of elements with the notation   number of quarters  number of dimes  number of nickels  number of cents   The intuition behind the construction can be read off of an example  parts 51

User · Answer

I know this is a very old question  I was searching through the proper answer and couldn t find anything that is simple and satisfactory  Took me some time but was able to jot down something   function denomination coins  original amount       var original amount   original amount      var original best             for var i 0 i lt coins length  i           var amount   original amount        var best              var tempBest             while coins i  lt  amount           amount   amount - coins i           best push coins i                  if amount gt 0  amp  amp  coins length gt 1           tempBest   denomination coins slice 0 i  concat coins slice i 1 coins length    amount             best   best concat denomination coins splice i 1   amount                  if tempBest length  0     best length  0  amp  amp  amount  0            best   best concat tempBest           if original best length  0              original best   best          else if original best length  gt  best length              original best   best                                return original best          denomination   1 10 3 9    19      This is a javascript solution and uses recursion

User · Answer

public class Coins    static int ac   421  static int bc   311  static int cc   11   static int target   4000   public static void main String   args          method2         public static void method2          running time n 2      int da   target ac      int db   target bc            for int i 0 i lt  da i                      for int j 0 j lt  db j                              int rem   target- i ac j bc                              if rem  lt  0                                       break                                 else                                    if rem cc  0                                         System out format   n d   d   d ----  d    d    d    d  n   i  j  rem cc  i ac  j bc   rem cc  cc  target

User · Answer

I looked into this once a long time ago  and you can read my little write-up on it  Here   s the Mathematica source   By using generating functions  you can get a closed-form constant-time solution to the problem  Graham  Knuth  and Patashnik   s Concrete Mathematics is the book for this  and contains a fairly extensive discussion of the problem  Essentially you define a polynomial where the nth coefficient is the number of ways of making change for n dollars   Pages 4-5 of the writeup show how you can use Mathematica  or any other convenient computer algebra system  to compute the answer for 10 10 6 dollars in a couple seconds in three lines of code    And this was long enough ago that that   s a couple of seconds on a 75Mhz Pentium

User · Answer

short and sweet with O n  table memory       include  lt iostream gt   include  lt vector gt   int count  std  vector lt int gt  s  int n       std  vector lt int gt  table n 1 0      table 0    1    for   auto amp  k   s       for int j k  j lt  n    j        table j     table j-k      return table n      int main       std  cout  lt  lt   count  25  10  5  1   100   lt  lt  std  endl    return 0

User · Answer

semi-hack to get around the unique combination problem - force descending order    denoms    1 5 10 25  def all combs sum last     return 1 if sum    0   return  denoms select  d  d  le sum    d  le last  inject 0    total denom             total all combs sum-denom denom   end   This will run slow since it won t be memoized  but you get the idea

User · Answer

PHP Code to breakdown an amount into denominations     Define the denominations     private  denominations   array 1000  500  200  100  50  40  20  10  5  1          S  countDenomination   function         author Edwin Mugendi  lt edwinmugendi gmail com gt         Count denomination         param float  original amount Original amount         return array with denomination and count     public function countDenomination  original amount         amount    original amount       denomination count array   array        foreach   this- gt denominations as  single denomination              count   floor  amount    single denomination             denomination count array  single denomination     count            amount   fmod  amount   single denomination          E  foreach statement      var dump  denomination count array       return  denomination count array        return  denomination count array        E  countDenomination   function

User · Answer

I would favor a recursive solution   You have some list of denominations  if the smallest one can evenly divide any remaining currency amount  this should work fine   Basically  you move from largest to smallest denominations  Recursively    You have a current total to fill  and a largest denomination  with more than 1 left   If there is only 1 denomination left  there is only one way to fill the total   You can use 0 to k copies of your current denomination such that k   cur denomination  lt   total  For 0 to k  call the function with the modified total and new largest denomination  Add up the results from 0 to k   That s how many ways you can fill your total from the current denomination on down   Return this number    Here s my python version of your stated problem  for 200 cents   I get 1463 ways   This version prints all the combinations and the final count total      usr bin python    find the number of ways to reach a total with the given number of combinations  cents   200 denominations    25  10  5  1  names    25   quarter s    10   dime s    5    nickel s    1    pennies    def count combs left  i  comb  add       if add  comb append add      if left    0 or  i 1     len denominations           if  i 1     len denominations  and left  gt  0             if left   denominations i                  return 0            comb append   left denominations i   demoninations i                i    1         while i  lt  len denominations               comb append   0  denominations i                 i    1         print     join   d  s     n names c   for  n c  in comb           return 1     cur   denominations i      return sum count combs left-x cur  i 1  comb      x cur   for x in range 0  int left cur  1    count combs cents  0      None

[algorithm] How to find all combinations of coins when given some dollar value

Examples related to algorithm

Examples related to recursion

Examples related to puzzle

Examples related to coin-change