Solution algorithm and thought process

• 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 `amount`?")

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[0], 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 `coins`.

Dynamic Programming

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 `i`th 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 `amount`.

``````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 `combinations` function.

``````def combinations_dp(amount, coins):
results = []
clen1 = len(coins) + 1
results.append([1]*clen1)
for a in range(1, amount + 1):
results.append([0]*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][0]
``````

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([1] + [0]*(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[0][amount%coins[0]]
``````

Now the space-complexity is O(m min(k, n)) where k is the size of the biggest coin.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.