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]

Answer 2

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!

Answer 3

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]

Answer 4

This is an variant of subset-sum problem. In your problem, you can pick an item several times. You still can use a similar idea to solve this problem by using the dynamic prorgamming technique. The basic idea is to design a function F(k, j), such that F(k, j) = 1 means that there is a sequence from arr whose sum is j and length is k.

Formally, the base case is that F(k, 1) = 1, if there exists an i, such that arr[i] = k. For inductive case, F(k, j) = 1, if there exists an i, such that arr[i] = m, and F(k-1, j-m) = 1.

The smallest k with F(k, n) = 1 is the length of the shortest sequence you want.

By using the dynamic programming technique, you can compute function F without using recursion. By tracking additional information for every F(k, j), you also can reconstruct the shortest sequence.