Skip to content
Advertisement

Using Recursion to check for sum of tuples in a list

I have a func which takes a list of tuples, each tuple contains two items: item name and value. I need the func to return True if it’s possible to divide the tuple list into two equal valued groups and False otherwise. The function should be recursive and should not use any loops.

for example,

func([('tree', 500), ('keyboard', 200), ('pen', 300)])

should result in True, because the value of keyboard + pen = tree and it can be divided into two equal groups.

So far, what I managed to write is:

def func(lst):
if len(lst) == 1 or len(lst) == 0:
    return False
elif len(lst) == 2:
    if lst[0][1] != lst[1][1]:
        return False
    else:
        return True

But it only covers the basic cases. Any help would be appreicated.

Advertisement

Answer

Not very efficient for big lists, but I assume it is recursive because of school work:

def divide(lst, left_sum, right_sum):
    # if no more elements,
    # then it is true if  left_sum == right_sum else false
    if not lst:
        return left_sum == right_sum

    obj, value = lst[0]
    # element can go either left or right
    return divide(lst[1:],left_sum + value, right_sum) or divide(lst[1:],left_sum, right_sum+value)

assert divide([('tree', 500), ('keyboard', 200), ('pen', 300)],0,0)
assert not divide([('tree', 500), ('keyboard', 200), ('pen', 301)],0,0)
Advertisement