What you're trying to solve is a variant of the coin change problem. Here you're looking for smallest amount of change, or the minimum amount of coins that sum up to a given amount.
Consider a simple case where your array is
c = [1, 2, 3]
you write 5 as a combination of elements from C and want to know what is the shortest such combination. Here C is the set of coin values and 5 is the amount for which you want to get change.
Let's write down all possible combinations:
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 2 + 2
1 + 1 + 3
2 + 3
Note that two combinations are the same up to re-ordering, so for instance 2 + 3 = 3 + 2.
Here there is an awesome result that's not obvious at first sight but it's very easy to prove. If you have any sequence of coins/values that is a sequence of minimum length that sums up to a given amount, no matter how you split this sequence the two parts will also be sequences of minimum length for the respective amounts.
For instance if c[3] + c[1] + c[2] + c[7] + c[2] + c[3] add up to S and we know that 6 is the minimal length of any sequence of elements from c that add up to S then if you split
|
S = c[3] + c[1] + c[2] + c[7] | + c[2] + c[3]
|
you have that 4 is the minimal length for sequences that add up to c[3] + c[1] + c[2] + c[7] and 2 the minimal length for sequences that add up to c[2] + c[3].
|
S = c[3] + c[1] + c[2] + c[7] | + c[2] + c[3]
|
= S_left + S_right
How to prove this? By contradiction, assume that the length of S_left is not optimal, that is there's a shorter sequence that adds up to S_left. But then we could write S as a sum of this shorter sequence and S_right, thus contradicting the fact that the length of S is minimal. □
Since this is true no matter how you split the sequence, you can use this result to build a recursive algorithm that follows the principles of dynamic programming paradigm (solving smaller problems while possibly skipping computations that won't be used, memoization or keeping track of computed values, and finally combining the results).
Because of this property of maintaining optimality for subproblems, the coins problem is also said to "exhibit optimal substructure".
OK, so in the small example above this is how we would go about solving the problem with a dynamic programming approach: assume we want to find the shortest sequence of elements from c = [1, 2, 3] for writing the sum 5. We solve the subproblems obtained by subtracting one coin: 5 - 1, 5 - 2, and 5 - 3, we take the smallest solution of these subproblems and add 1 (the missing coin).
So we can write something like
shortest_seq_length([1, 2, 3], 5) =
min( shortest_seq_length([1, 2, 3], 5-1),
shortest_seq_length([1, 2, 3], 5-2),
shortest_seq_length([1, 2, 3], 5-3)
) + 1
It is convenient to write the algorithm bottom-up, starting from smaller values of the sums that can be saved and used to form bigger sums. We just solve the problem for all possible values starting from 1 and going up to the desired sum.
Here's the code in Python:
def shortest_seq_length(c, S):
res = {0: 0} # res contains computed results res[i] = shortest_seq_length(c, i)
for i in range(1, S+1):
res[i] = min([res[i-x] for x in c if x<=i]) + 1
return res[S]
Now this works except for the cases when we cannot fill the memoization structure for all values of i. This is the case when we don't have the value 1 in c, so for instance we cannot form the sum 1 if c = [2, 5] and with the above function we get
shortest_seq_length([2, 3], 5)
# ValueError: min() arg is an empty sequence
So to take care of this issue one could for instance use a try/catch:
def shortest_seq_length(c, S):
res = {0: 0} # res contains results for each sum res[i] = shortest_seq_length(c, i)
for i in range(1, S+1):
try:
res[i] = min([res[i-x] for x in c if x<=i and res[i-x] is not None]) +1
except:
res[i] = None # takes care of error when [res[i-x] for x in c if x<=i] is empty
return res[S]
Or without try/catch:
def shortest_seq_length(c, S):
res = {0: 0} # res[i] = shortest_seq_length(c, i)
for i in range(1, S+1):
prev = [res[i-x] for x in c if x<=i and res[i-x] is not None]
if len(prev)>0:
res[i] = min(prev) +1
else:
res[i] = None # takes care of error when [res[i-x] for x in c if x<=i] is empty
return res[S]
Try it out:
print(shortest_seq_length([2, 3], 5))
# 2
print(shortest_seq_length([1, 5, 10, 25], 37))
# 4
print(shortest_seq_length([1, 5, 10], 30))
# 3
print(shortest_seq_length([1, 5, 10], 25))
# 3
print(shortest_seq_length([1, 5, 10], 29))
# 7
print(shortest_seq_length([5, 10], 9))
# None
To show not only the length but also the combinations of coins of minimal length:
from collections import defaultdict
def shortest_seq_length(coins, sum):
combos = defaultdict(list)
combos[0] = [[]]
for i in range(1, sum+1):
for x in coins:
if x<=i and combos[i-x] is not None:
for p in combos[i-x]:
comb = sorted(p + [x])
if comb not in combos[i]:
combos[i].append(comb)
if len(combos[i])>0:
m = (min(map(len,combos[i])))
combos[i] = [combo for i, combo in enumerate(combos[i]) if len(combo) == m]
else:
combos[i] = None
return combos[sum]
total = 9
coin_sizes = [10, 8, 5, 4, 1]
shortest_seq_length(coin_sizes, total)
# [[1, 8], [4, 5]]
To show all sequences remove the minumum computation:
from collections import defaultdict
def all_seq_length(coins, sum):
combos = defaultdict(list)
combos[0] = [[]]
for i in range(1, sum+1):
for x in coins:
if x<=i and combos[i-x] is not None:
for p in combos[i-x]:
comb = sorted(p + [x])
if comb not in combos[i]:
combos[i].append(comb)
if len(combos[i])==0:
combos[i] = None
return combos[sum]
total = 9
coin_sizes = [10, 5, 4, 8, 1]
all_seq_length(coin_sizes, total)
# [[4, 5],
# [1, 1, 1, 1, 5],
# [1, 4, 4],
# [1, 1, 1, 1, 1, 4],
# [1, 8],
# [1, 1, 1, 1, 1, 1, 1, 1, 1]]
One small improvement to the algorithm is to skip the step of computing the minimum when the sum is equal to one of the values/coins, but this can be done better if we write a loop to compute the minimum. This however doesn't improve the overall complexity that's O(mS) where m = len(c).
