Adi_S Adi_S - 12 days ago 5
Python Question

Getting the number of matching sums in a list using recursion

def number_ties(my_list, for_it=[], against=[],ties=0,k=0):
if len(my_list)==0:
return ties
j=my_list[0]
del my_list[0]
if sum(list(for_it))==sum(list(against)) and k>0:
ties+=1
k+=1
return number_ties(my_list,for_it+[j],against,ties,k)+number_ties(my_list,for_it,against+[j],ties,k)


Using recursion, I'm trying to take a list of numbers and find out how many ways I can put different combinations of these numbers for and against something ( a vote for example ) and achieve a tie. For example [1,2,3] can tie in 2 ways i.e [1,2] against [3] and [3] against [1,2]. Similarly [1, 1, 2, 3, 5] should tie in 4 ways. ( Same numbers within the list should be considered different votes.Like people with different voting weights, for example.)
My code above doesnt work. How may I fix it?

Answer

The resulting problem of summing up combinations to half the total sum of your list is more suitable for a recursive implementation:

def number_ties(lst):
    s = sum(lst)
    if s % 2:
        return 0  # sum must be even for it to work at all
    half = s // 2
    return sum_count(lst, half)


def sum_count(lst, total):  # number of combinations out of lst that sum to total
    if not lst:  # base case
        return int(total == 0)  # empty lst and total 0 -> return 1
    # recur: add ways with first element and ways without
    return sum_count(lst[1:], total) + sum_count(lst[1:], total-lst[0])

> print(number_ties([1, 2, 3]))
2
> print(number_ties([1, 1, 2, 3, 5]))
4
Comments