Finding shortest combinations in array/sequence that equals sum

Question

I'm totally stuck and have no idea how to go about solving this. Let's say I've an array

arr = [1, 4, 5, 10]

and a number

n = 8

I need shortest sequence from within arr which equals n. So for example following sequences within arr equals n

c1 = 5,1,1,1
c2 = 4,4
c3= 1,1,1,1,1,1,1,1

So in above case, our answer is c2 because it's shortest sequences in arr that equals sum.

I'm not sure what's the simplest way of finding a solution to above? Any ideas, or help will be really appreciated.

Thanks!

Edited:

• Fixed the array
• Array will possibly have postive values only.
• I'm not sure how subset problem fixes this, probably due to my own ignorance. Does sub-set algorithm always give the shortest sequence that equals sum? For example, will subset problem identify c2 as the answer in above scenario?

Answer 1

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]