Select all elements from a python list that adds upto a particular targer number [not two sum problem]

Question

I have a python list like the following:

sample_list = [20, 15, 35, 50, 2, 300, 225] 
target_value = 200

Now, I want to write a python program that returns a list containing all the elements those total should be less than the target_value and the closest value of target_value. In the case of the mentioned example, the function should return the following list:

[20, 15, 35, 50, 2]

As 2+15+20+35+50 = 122 which is less than target_value = 200 but if I add any other value (300/225), it would be larger than 200.

I'm looking for a very optimized solution for this problem.

Answer 1

This is the classic closest sum problem. It lends itself to a dynamic programming algorithm. The following solution has a complexity of O(n.k) where n is the length of the array and k is the desired threshold. This implementation uses a dynamic dictionary, although the same can be done with a dynamic 2D list.

def closestSum(arr, k):
    #create a dp dictionary to grow. key is closest sum so far, value is the list of numbers that add up to key
    dp_dict = {0:[]}

    for num in arr:
        dict_copy = dict(dp_dict)
        # grow or update the dp dict with the closest sum so far
        for sum in dp_dict:
            if sum + num < k:
                dict_copy[sum+num] = dp_dict[sum]+[num]
        dp_dict = dict_copy

    #traceback - find the item in dp dict that is closest to k
    result = (k,[])
    for sum, number_list in dp_dict.items():
        distance = abs(k - sum)
        if distance < result[0]:
            result = (distance, number_list)
    return result[1]

sample_list = [20, 15, 35, 50, 2, 300, 225]
target_value = 200
print(closestSum(sample_list, target_value))
#[20, 15, 35, 50, 2]

Answer 2

I don't know if this is the most efficient way of doing it, but it definetly works:

from itertools import combinations

scores = {}
sample_list = [20, 15, 35, 50, 2, 300, 225]
target_value = 200
sample_list = [a for a in sample_list if a <= target_value]

for i in range(len(sample_list)):
    for combination in combinations(sample_list, i + 1):
        if sum(combination) <= target_value:
            scores[sum(combination)] = combination

print(list(scores[max(scores.keys())])) # [20, 15, 35, 50, 2]

To make it more efficient you could break the loop if any combination reaches the target value, since it will be the highest. But since this is a pretty unlikely scenario, it won't change the overall efficiency.

Answer 3

Is this the solution you were looking for?

sample_list = [20, 15, 35, 300, 50, 2, 70, 199]
target_value = 200

editable_list = sample_list
final_list=[]
current_value = 0

for i in editable_list:
    absolute_difference_function = lambda list_value : abs(list_value - target_value)
    closest_value = min(editable_list, key=absolute_difference_function)

    if current_value + closest_value > target_value:
        editable_list.remove(closest_value)

    else:
        current_value += closest_value
        final_list.append(closest_value)
        editable_list.remove(closest_value)


print(final_list)

Answer 4

I think this can be done much simpler:

def sum_until(nums, target):
    solution = []
    for num in nums:
        if sum(solution) < target and (sum(solution) + num) < target;
            solution.append(num)
        else:
            break
    return solution