A set which forms a matroid (https://en.wikipedia.org/wiki/Matroid) can be used to solve the coin changing problem by using greedy approach. In brief, a matroid is an ordered pair M = (S,l) satisfying the following conditions: S is a finite nonempty set l is a nonempty family of subsets of S, called the independent subsets,such that … Read more
“number (N) of ways … using N kinds” these two Ns are clearly not the same. so let’s say K kinds of coins. We have many coins, but each coin is either 1, 5, 10, 25 or 50 cents, in total 5 kinds of coins. We need to buy something for a dollar, 100 cents. … Read more
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 … Read more