Sum of value in array and condition check - Python

Question

I have the following variables:

arr = [50, 100, 100, 100, 200, 200]
inp = 450

in the inp variable, I receive data from the user, the user can enter any value between the minimum array and the maximum amount of values in the array (50 and 750).

I want to return the values in the array that make up the amount equal to the value in the variable inp

In this situation inp = 450 there are two variants: 50 + 100 + 100 + 200 or 50 + 200 + 200. I'm only interested in one of them.

how can i continue the following code:

import sys

arr = [50, 100, 100, 100, 200, 200]
inp = 450
sum = 0
res = []

for x in arr:
    if x == inp:
        res = x
        print(res)
        sys.exit()

    sum = sum+x
    res.append(x)

    if sum == inp:
        print(res)
        sys.exit()

I can solve the problem if I make six loops, but if the length of the array changes I have to intervene on the source code. I'm looking for a recursive solution.

Answer 1

I would use the itertools.combinations API. You could also use a generator to allow finding all of the values, or choose to stop at the first:

import itertools


def find_comb_for_sum(data, total):
    for i in range(len(data)):
        for comb in itertools.combinations(data, i + 1):
            if sum(comb) == total:
                yield comb

This will find all combinations of the array starting from least amount of entries per combination to most. Reverse the range range(len(data))[::-1] if you'd like to do the opposite.

Some test cases:

arr = [50, 100, 100, 100, 200, 200]
inp = 450

comb = find_comb_for_sum(arr, inp)
print(f"Matching combination for {arr} summing to {inp} is: {next(comb, None)}")

arr = [50, 100, 100, 100, 200, 200]
inp = 444

comb = find_comb_for_sum(arr, inp)
print(f"Matching combination for {arr} summing to {inp} is: {next(comb, None)}")

Matching combination for [50, 100, 100, 100, 200, 200] summing to 450 is: (50, 200, 200)
Matching combination for [50, 100, 100, 100, 200, 200] summing to 444 is: None