使用递归确定半完美数

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)

但是，这个函数不知道什么时候停止。所以我们需要一些基本案例。

显然，如果 sum 为 0，答案就是肯定的：

if sum_left == 0:
    return True

另一个基本情况是，如果总和是 < 0, we have taken a too big element and we can never recover.

if sum_left < 0:
    return False

此外，我们可能会冒用完元素的风险，例如 [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)