时间戳

首页 > 解决方案 > 从没有循环的列表中求和

python - 从没有循环的列表中求和

问题描述

所以我正在研究递归并且必须编写一些不使用循环的代码

对于我的代码的一部分，我想检查是否可以将列表的子集总结为特定数字，如果可以，则返回列表中这些数字的索引。

例如，如果列表是 [5,40,20,20,20] 并且我用数字 60 发送它，我希望我的输出是 [1,2]，因为 40+20=60。万一我不能得到这个数字，输出应该是一个空列表。

我从

def find_sum(num,lst,i,sub_lst_sum,index_lst):  
if num == sub_lst_sum:
    return index_lst
if i == len(sum): ## finished going over the list without getting to the sum
    return []
if sub_lst_sum+lst[i] > num:
    return find_sum(num,lst,i+1,sub_lst_sum,index_lst)
return ?..

index_lst = find_sum(60,[5,40,20,20,20],0,0,[])

num是我要总结的数字，

lst是数字列表

最后一次返回应该涵盖我计算列表中的当前数字而不计算它的选项..（否则在示例中它将采用五个并且将没有解决方案）。我不知道该怎么做..

标签： pythonrecursion

解决方案

这里有一个提示。也许最简单的方法是考虑以下归纳推理来指导您的递归。

如果

index_list = find_sum(num,lst,i+1)

然后

index_list = find_sum(num,lst,i)

也就是说，如果索引列表可用于使用从位置开始的num元素构造和i+1，那么当使用从位置开始的元素时，它也是一种解决方案i。这么多应该很清楚。第二个归纳推理是，

如果

index_list = find_sum(num-lst[i],lst,i+1)

然后

[i]+index_list = find_sum(num,lst,i)

也就是说，如果索引列表可用于num-lst[i]使用从 positioni+1开始的元素返回总和，那么您可以使用它来构建索引列表，其各个元素的总和是num通过附加i.

这两位归纳推理可以转化为两个递归调用来解决问题。我写的第一个也应该用于第二个递归调用，而不是第一个（问题：为什么？）。

此外，对于没有解决方案的基本情况，您可能需要重新考虑使用空列表。这可以工作，但是您作为解决方案返回一个不是解决方案的列表。在 python 中，我认为None这是一个标准的惯用选择（但你可能想与比我更精通 python 的人仔细检查）。

填空

def find_sum(num,lst,i):  
    if num == 0  :
        return []
    elif i == len(lst) :
        return None 
    else :
        ixs = find_sum(???,lst,i+1)
        if ixs != None :
            return ???
        else :
            return find_sum(???,lst,i+1)

推荐阅读