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)