Coin Change, Part 3
May 24, 2013
Our exercise today is similar to the two previous exercises on the coin change problem, but doesn’t directly involve coins. But we’ll still call it a coin change problem because I can’t think of a better name.
As in the coin change problems, we are given a target to which a set of coins is intended to sum. But instead of a list of coins, we are given a number n and assume that we have one of each denomination of coin from 1 through n. Unlike the coin change problems, we have only one of each coin, not an infinite number of them.
The problem is to figure out all the ways to combine coins to reach the desired sum. For instance, if the sum s is 10 and n is 10, the ways to combine the coins are (10), (9 1), (8 2), (7 3), (7 2 1), (6 4), (6 3 1), (5 4 1), (5 3 2), and (4 3 2 1). Note that a set like (6 2 2) is not possible because only one 2-coin is available. As in the two previous exercises, we are interested in both a function to make a list of all the solutions and a separate function that simply counts them.
Your task is to write the two programs described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Memoized/dynamic programming solution, in clojure, should use O(sn) space and time:
(ns coins3) ; what ways to pay "s" with exactly one of each coin from 1 to n? (def pay (memoize (fn [s n] (cond (zero? s) '(()) ; only one way to pay 0 (< s n) (recur s s) ; can't use any coin larger than s :else ; pay part, then pay the remainder with smaller coins (mapcat (fn [c] (map #(conj % c) (pay (- s c) (dec c)))) (range n 0 -1)))))) ; try big coins first, to match outputHm. Looking at it again, “recur” in line 7 above could “dodge” the memoization; should replace that with “pay” instead.
It’s more space-efficient yet to extract the “else” clause into a mutually-recursive function and memoize it separately, or, as in the sample solution, to explicitly solve via dynamic programming.
An O(S*N) time and O(S) space solution that counts the number of ways the sum can be obtained: