title: Dynamic change-making algorithm that returns actual list of coins used
body: <p>I'm trying to adjust the code from the wikipedia:</p>
  
  <p><a href="https://en.wikipedia.org/wiki/Change-making_problem#Implementation" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Change-making_problem#Implementation</a></p>
  
  <p>To also output the list of coins used, not only the number of coins used. That is, for instance:</p>
  
  <p><code>change_making([6, 8, 12], 52)</code> outputs <code>5</code> which is correct (<code>12+12+12+8+8 = 52</code>).</p>
  
  <p>The problem is that I want to get output in this format <code>[12, 12, 12, 8, 8]</code> instead of just <code>5</code> and I have no idea how to do that.</p>
  
  <p>The code in question:</p>
  
  <pre><code>def _get_change_making_matrix(set_of_coins, r):
      m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)]
  
      for i in range(r + 1):
          m[0][i] = i
  
      return m
  
  
  def change_making(coins, n):
      """This function assumes that all coins are available infinitely.
  
      n is the number that we need to obtain with the fewest number of coins.
  
      coins is a list or tuple with the available denominations."""
  
      m = _get_change_making_matrix(coins, n)
  
      for c in range(1, len(coins) + 1):
  
          for r in range(1, n + 1):
  
              # Just use the coin coins[c - 1].
              if coins[c - 1] == r:
                  m[c][r] = 1
  
              # coins[c - 1] cannot be included.
              # We use the previous solution for making r,
              # excluding coins[c - 1].
              elif coins[c - 1] &gt; r:
                  m[c][r] = m[c - 1][r]
  
              # We can use coins[c - 1].
              # We need to decide which one of the following solutions is the best:
              # 1. Using the previous solution for making r (without using coins[c - 1]).
              # 2. Using the previous solution for making r - coins[c - 1] (without using coins[c - 1]) plus this 1 extra coin.
              else:
                  m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])
  
      return m[-1][-1]
  </code></pre>
  
  <p>Any help/suggestion would be greatly appreciated.</p>
  
  <p>------------- EDIT -------------</p>
  
  <p>The solution (comments removed):</p>
  
  <pre><code>def _change_making(coins, n):
      m = [[0 for _ in range(n + 1)] for _ in range(len(coins) + 1)]
      for i in range(n + 1):
          m[0][i] = i
  
      for c in range(1, len(coins) + 1):
          for r in range(1, n + 1):
              if coins[c - 1] == r:
                  m[c][r] = 1
              elif coins[c - 1] &gt; r:
                  m[c][r] = m[c - 1][r]
              else:
                  m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]])
  
      i = len(coins)
      j = n
      ret = {k: 0 for k in coins}
      while j != 0:
          if m[i][j - coins[i - 1]] == m[i][j] - 1:
              ret[coins[i - 1]] += 1
              j = j - coins[i - 1]
          else:
              i = i - 1
  
      return ret
  </code></pre>
  
  <p>To find the <em>closest</em> * solution:</p>
  
  <pre><code>def change_making(coins, n):
      try:
          return _generate_packing(coins, n)
      except:
          return generate_packing(coins, n + 1)
  </code></pre>
  
  <p>For instance <code>change_making([2, 5], 8)</code></p>
  
  <pre><code>{2: 2, 5: 1}
  </code></pre>
  
  <p>Because 9 is the closest possible solution.</p>
  
  <ul>
  <li>By <em>closest</em> I mean a solution that is possible to satisfy but above the original request. For instance if we need to return £8 in change and we do not have the exact change, well, we will return £9 because we do have change for that.</li>
  </ul>