How would I edit this greedy function to give me a sum?

Question

So, I want to create a function that takes int s and array A, and then returns array of elements A that add up to s. if no subset, should return value closest to s.

For example:

A = [12, 79, 99, 91, 81, 47]
s = 150

Will return:

[12, 91, 47]

as 12 + 91 + 47 is 150.

The below is what I have so far. What am I doing wrong?

def closest(s, A):
    if s == 0:
        return 0
    for i in range(len(A)):
        if A[i] <= s:
            return 1 + closest(s - A[i], A)

Possible duplicate of [Find all combinations of a list of numbers with a given sum](https://stackoverflow.com/questions/34517540/find-all-combinations-of-a-list-of-numbers-with-a-given-sum) — rahlf23, Nov 01 '18 at 20:31
You're using `return` in a `for` loop which will break out of the function the first time the condition is `True` (I.e. a single value) — roganjosh, Nov 01 '18 at 20:33

RealRageDontQuit · Answer 1 · 2018-11-01T21:04:13.803

This has been answer before

Find all combinations of a list of numbers with a given sum

in your case code is:

import itertools

def itersum(nums, target):

    result = [seq for i in range(len(nums),0,-1) for seq in itertools.combinations(nums,i) if sum(seq) == target]
    if result != target:
       for j in range(target):
           result1 = [seq for i in range(len(nums),0,-1) for seq in itertools.combinations(nums,i) if sum(seq) == target + j]
           result2 = [seq for i in range(len(nums),0,-1) for seq in itertools.combinations(nums,i) if sum(seq) == target - j]
           if (len(result1) + len(result2)) > 0:
               result = result1 if result1 > result2 else result2
               break            
    return result

A = [12, 79, 99, 91, 81, 44]

s = 150

itersum(A, s)

score 0 · Answer 2 · answered Nov 01 '18 at 21:06

The function should return a list of lists instead because there could be more than one combination that adds up to the given sum:

def closest(s, A):
    if s == 0:
        return [[]]
    o = []
    for i, n in enumerate(A):
        if n <= s:
            for c in closest(s - n, A[i + 1:]):
                o.append([n] + c)
    return o

so that:

closest(150, [12, 79, 99, 91, 81, 47])

returns:

[[12, 91, 47]]

and that:

closest(10, [4, 5, 6, 2, 1, 3])

returns:

[[4, 5, 1], [4, 6], [4, 2, 1, 3], [5, 2, 3], [6, 1, 3]]

How would I edit this greedy function to give me a sum?

2 Answers2