One of the first thing to do about a problem like this is to try to construct a recursive solution (without worrying about optimality). That is, try to break it down into smaller sub-problems.
The correct recursive solution to this problem is not very obvious, because enumerating combinations is not very straightforward. So first, instead of combinations, let's construct a recursive solution enumerating permutations of coins that add up to
amount. (In other words, "How many possible sequences of coins exist that add up to
Counting Valid Permutations
Let's construct a (recursive) function that returns the number of possible coin-sequences given an
amount and possible coin choices. At each step, for each possible coin choice, we call the function recursively with the reduced amount, and return the sum of all recursive calls. Terminating conditions: return 1 if
amount == 0, or return 0 if
amount < 0.
def permutations(amount, coins): if amount < 0: return 0 elif amount == 0: return 1 sum = 0 for coin in coins: sum += permutations(amount - coin, coins) return sum
This has an exponential time complexity of O(m^n) where m is the number of coins and n is the amount.
From Permutations to Combinations
Let's take an example:
amount = 12,
coins = [1,2,5]. When these values are passed to the above
permutations function, a tree of recursive calls are made where each path down the tree indicate a particular sequence of coins.
12 1/ |2 \5 11 10 7 /|\ /|\ /|\ ... ... ...
Sequences such as
1 5 2 2 1 1 or
5 1 5 5 or
2 2 2 1 2 2 2 are all included in that tree.
One valid way to enumerate combinations, is to constrain sequences to be only of the form
1 1 1 2 2 5 or
1 5 5 5 or
1 2 2 2 2 2 2 (i.e.
1s 2s 5s). Once this key observation is made, the recursive solution is fairly easy to construct.
def combinations(amount, coins): if amount < 0: return 0 elif amount == 0: return 1 if len(coins) == 0: return 0 # use the first coin sum = combinations(amount - coins, coins) # stop using the first coin sum += combinations(amount, coins[1:]) return sum
That's it! That's our recursive solution to the problem with a time complexity of O(2^n).
Sidenote: The space complexity is also exponential for the above program because a copy of
coins with one element fewer is created in each call. But that copy can be easily avoided by having an additional argument indicating offset index in
When there are large overlaps in the tree of recursive calls (i.e. if many duplicate function calls having identical arguments are made), then storing the results of those intermediate calls and reusing them as needed will most definitely save time. This technique is called Dynamic Programming or Dynamic Optimization ("dynamic" as in "at runtime").
As a warm up, let's rewrite our
permutations function using Dynamic Programming. First we note that among the arguments,
amount varies from its initial value all the way till zero (or slightly negative) as we recurse deeper, while
coins remain the same. So we just need to create a 1-D array having a length of (initial)
amount + 1 whose
ith element stores the result of
permutations(i, coins). This array will be populated bottom-up, that is, from the base case (zero
amount) and up till we reach the target
def permutations_dp(amount, coins): results =  results.append(1) # case when amount is 0 for a in range(amount + 1): # a from 0 to amount (incl) results.append(0) for coin in coins: if a - coin >= 0: results[a] += results[a - coin] return results[amount]
This has a time complexity of O(mn) and space complexity of O(n).
Below is a straightforward DP rewrite of our
def combinations_dp(amount, coins): results =  clen1 = len(coins) + 1 results.append(*clen1) for a in range(1, amount + 1): results.append(*clen1) for ci in reversed(range(clen1-1)): if a - coins[ci] >= 0: results[a][ci] = results[a - coins[ci]][ci] results[a][ci] += results[a][ci+1] return results[amount]
This has a time and space complexity of O(mn), which can still be optimized for space.
Observe that, in column
i, we only need the last
coins[i] values to calculate the values in future rows.
def combinations_dp(self, amount, coins): clen = len(coins) if clen == 0: return 1 if amount == 0 else 0 results =  for coin in coins: results.append( + *(coin - 1)) for a in range(1, amount + 1): for ci in reversed(range(clen - 1)): results[ci][a % coins[ci]] += results[ci+1][a % coins[ci+1]] return results[amount%coins]
Now the space-complexity is O(m min(k, n)) where k is the size of the biggest coin.