Finding shortest combinations in array/sequence that equals sum

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?

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]