Combining coins to reach a target sum (C, Python)

Alternatively, you can ask Wolfram Alpha to compute a power series: <a href="http://www.wolframalpha.com/input/?i=series+1%2F%28%281-x%29*%281-x%5E2%29*%281-x%5E5%29*%281-x%5E10%29*%281-x%5E20%29*%281-x%5E50%29*%281-x%5E100%29*%281-x%5E200%29%29+at+x%3D0+to+order+200" rel="nofollow">http://www.wolframalpha.com/input/?i=series+1%2F%28%281-x%29...</a>

FWIW, printf() is not async-signal-safe. It's bad form to call such routines from within a signal handler.<p>Here's a list of async-signal-safe functions (scroll down): <a href="http://pubs.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_04.html" rel="nofollow">http://pubs.opengroup.org/onlinepubs/009695399/functions/xsh...</a><p>I know I'm missing the point of the post, but it is a particular nit that I pick. You'd be surprised at how often this happens in production code, and how often it causes mysterious, hard-to-reproduce bugs.

This problem is closely related to the Frobenius coin problem: <a href="http://en.wikipedia.org/wiki/Coin_problem" rel="nofollow">http://en.wikipedia.org/wiki/Coin_problem</a><p>It's an interesting problem. My gut reaction was to solve X1 + X2 + (...) + X6 = 200; X1, ..., X6 &#60; 0, which would be C(205, 200), but that ignores the denominations of each coin, so it doesn't really generate what you want.

It's possible to do this using just a one-dimensional array. Since we only need the last column of the matrix we calculated to calculate the next column, the array can be updated in-place.<p><pre><code> coins = [1, 2, 5, 10, 20, 50, 100, 200] total = 200 matrix = [0] * (total + 1) matrix[0] = 1 for coin in coins: for j in range(coin, len(matrix)): matrix[j] += matrix[j - coin]</code></pre>

`[(y,x)]` is the same thing as `[y,x]`<p>`,` creates a tuple, not parentheses (empty tuple is an exception).

Very nice example of memoization.