If the question is asking how many possible solutions there are, it can be solved with generating functions. (This method was popularized by George Pólya but I

If the question is asking how many possible solutions there are, it can be solved with generating functions. (This method was popularized by George Pólya but I learned it from Knuth.) Let A(z) be the generating function for the number of ways to spend n cents using only the $1.22 yoyo. Then naturally we can only spend those n that are multiples of 122 cents. So we define A(z) = 1 + z^122 + z^244 + z^366 + ... In this formulation the coefficient represents the number of ways: that's why the coefficient is 1 if the power is a multiple of 122 but 0 otherwise. Next we realize this infinite sum can be transformed into A(z) = 1 / (1 - z^122). Next, we consider what happens if we are allowed to use both the $1.22 yoyo and $2.75 doll. We get B(z) = 1 / (1 - z^275) * A(z). We repeat this for all items, to arrive at the closed form solution U(z) = 1 / ((1 - z^122) * (1 - z^275) * (1 - z^185) * ... * (1 - z^87)) Now if we have a computer algebra system we just ask it to do a Taylor expansion and read off the solution at the z^4394 term. Mathematica can do it but sadly I can't get Wolfram Alpha to do it. The answer is 4794820. (This allows repetitions, and I think the author didn't allow repetitions. The author also missed the third item, the $1.85 duckie which is apparent from the posted code and the fact that there are references to 2^20 not 2^21.) If you don't have a computer algebra system you can of course solve it manually with dynamic programming: the coefficient of z^n for B(z) is equal to the coefficient of z^n for A(z) plus the coefficient of z^(n-275) for B(z). Just think about the distributive law for multiplication. But then for Hacker News, I guess dynamic programming is more preferred then: #include <array> #include <stdio.h> int main() { static constexpr std::array<int, 21> kItemPrices = { 122, 275, 185, 597, 647, 216, 713, 457, 146, 518, 316, 489, 711, 645, 477, 804, 671, 231, 621, 98, 87}; static std::array<std::array<int, 4395>, kItemPrices.size()> dp = {}; // Base case for (int j = 0; j <= 4394; j += kItemPrices[0]) dp[0][j] = 1; // Recurrence for (int i = 1; i < kItemPrices.size(); ++i) { for (int j = 0; j <= 4394; ++j) { dp[i][j] = dp[i - 1][j] + (j - kItemPrices[i] < 0 ? 0 : dp[i][j - kItemPrices[i]]); } } printf("%d\n", dp[20][4394]); }