用递归确定半完美数

Question

我再次需要你的帮助。我正在编写一个代码，通过返回一个布尔值来确定一个数是否为半完美数。所以首先我想我会列出一个数字的因子，不包括数字本身

def isSemiPerfect(n):
factor = []
for i in range(n-1, 0, -1):
    if n%i == 0:
        factor.append(i)

如果我查12号，它会回来的

factor = [1, 2, 3, 4, 6]

然后我需要编写一个代码，使用递归来检查是否添加了某些数字，它将等于12

True = 6 + 4 + 2 or 6 + 3 + 2 + 1

有人能告诉我如何使用递归进行试错吗？就像我总是从最大的数字开始，然后尝试下一个最大数字的路径，直到我尝试了所有的组合

我知道没有太多的事情要做，我只是希望你能告诉我如何有效地使用递归。谢谢大家!

Answer 1

你可以这样想

问题“1,2,3,4,6能加起来等于12吗？”

与“能[2,3,4,6]和11”或“能[2,3,4,6]和12”相同吗

一个使用第一个元素（和较低），另一个不使用第一个元素，和相同

因此，启动函数是：

def f(lst,sum_left):
    return f(lst[1:], sum_left-lst[0]) or f(lst[1:],sum_left)

但是，此函数不知道何时停止。所以我们需要一些基本情况

显然，如果总和为0，答案是肯定的：

if sum_left == 0:
    return true

另一种基本情况是，如果总和为<；0，我们使用了太大的元素，无法恢复

if sum_left < 0:
    return true

此外，我们可能会面临用尽元素的风险，例如[1,2]的总和永远不会达到50，因此如果列表中没有元素，我们将添加一个基本情况：

if not lst:
    return false

总而言之：

def f(lst, left):
    if left == 0:
        return True
    if left < 0:
        return False
    if not lst:
        return False
    
    return f(lst[1:],left-lst[0]) or f(lst[1:],left)