Adi_S - 2 years ago 89
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?

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
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download