使用递归获取列表中匹配和的数目

Question

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)

使用递归，我试图得到一个数字的列表，并找出有多少种方法可以将这些数字的不同组合用于支持或反对某件事情（例如投票），并实现平局。例如[1,2,3]可以用两种方式并列，即[1,2]对[3]和[3]对[1,2]。同样地[1，1，2，3，5]应该有4种方式。（清单中的相同数字应视为不同投票。就像例如，拥有不同投票权的人。） 我上面的代码不起作用。我该怎么修呢？在

Answer 1

由此产生的将组合求和为列表总和一半的问题更适合递归实现：

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

Answer 2

首先，将其转换为一个稍微简单的问题：您必须找到求和为数组和的一半的元素的组合。这称为subset sum problem。在

基本思想是“简单”。在

Given: array, target
Grab the first array element, array[0]
if target == 0
    success; you're done
else if target < 0
    failure
else  # recur both with and without the first element
    solution_with = recur using (array[1:end], target - array[0]);
                    append array[0]
    solution_not  = recur using (array[1:end], target)

这能让你动起来吗？ 重现