Finding shortest combinations in array/sequence that equals sum

For the benefit of people who find this question in future -

As Oscar Lopez and Priyank Bhatnagar, have pointed out, this is the coin change (change-giving, change-making) problem.

In general, the dynamic programming solution they have proposed is the optimal solution - both in terms of (provably!) always producing the required sum using the fewest items, and in terms of execution speed. If your basis numbers are arbitrary, then use the dynamic programming solution.

If your basis numbers are "nice", however, a simpler greedy algorithm will do.

For example, the Australian currency system uses denominations of $100, $50, $20, $10, $5, $2, $1, $0.50, $0.20, $0.10, $0.05. Optimal change can be given for any amount by repeatedly giving the largest unit of change possible until the remaining amount is zero (or less than five cents.)

Here's an instructive implementation of the greedy algorithm, illustrating the concept.

def greedy_give_change (denominations, amount):        
    # Sort from largest to smallest
    denominations = sorted(denominations, reverse=True)

    # number of each note/coin given
    change_given = list()

    for d in denominations:
        while amount > d:
            change_given.append(d)
            amount -= d

    return change_given

australian_coins = [100, 50, 20, 10, 5, 2, 1, 0.50, 0.20, 0.10, 0.05]
change = greedy_give_change(australian_coins, 313.37)
print (change)           # [100, 100, 100, 10, 2, 1, 0.2, 0.1, 0.05]
print (sum(change))      # 313.35

For the specific example in the original post (denominations = [1, 4, 5, 10] and amount = 8) the greedy solution is not optimal - it will give [5, 1, 1, 1]. But the greedy solution is much faster and simpler than the dynamic programming solution, so if you can use it, you should!

This is problem is known as Minimum coin change problem.

You can solve it by using dynamic programming. Here is the pseudo code :

Set MinCoin[i] equal to Infinity for all of i
MinCoin[0] = 0

For i = 1 to N // The number N
For j = 0 to M - 1 // M denominations given
// Number i is broken into i-Value[j] for which we already know the answer
// And we update if it gives us lesser value than previous known.
   If (Value[j] <= i and MinCoin[i-Value[j]]+1 < MinCoin[i])
       MinCoin[i] = MinCoin[i-Value[j]]+1

Output MinCoin[N]

As has been pointed before this is the minimum change coin problem, typically solved with dynamic programming. Here's a Python implementation solved in time complexity O(nC) and space complexity O(C), where n is the number of coins and C the required amount of money:

def min_change(V, C):
    table, solution = min_change_table(V, C)
    num_coins, coins = table[-1], []
    if num_coins == float('inf'):
        return []
    while C > 0:
        coins.append(V[solution[C]])
        C -= V[solution[C]]
    return coins

def min_change_table(V, C):
    m, n = C+1, len(V)
    table, solution = [0] * m, [0] * m
    for i in xrange(1, m):
        minNum, minIdx = float('inf'), -1
        for j in xrange(n):
            if V[j] <= i and 1 + table[i - V[j]] < minNum:
                minNum = 1 + table[i - V[j]]
                minIdx = j
        table[i] = minNum
        solution[i] = minIdx
    return (table, solution)

In the above functions V is the list of possible coins and C the required amount of money. Now when you call the min_change function the output is as expected:

min_change([1,4,5,10], 8)
> [4, 4]