您当前的代码正在返回解决方案的数目。在这两个基本情况之后,有两个递归调用。在第一个递归调用中,我们检查存在多少个解决方案。
X
不包括
current**N
. 第二个递归检查如果我们存在多少解
做
包括
当前**N
.
如果要返回实际的解决方案本身(作为元组列表),则需要稍微更改代码。
从基本情况开始。如果
pw > X
,没有解决方案
current
这么大,所以我们应该返回一个空列表。如果
pw == X
,然后我们找到了一个解决方案,应该返回一个单元素列表,其中包含单元素元组
(current,)
(注意后面的逗号,这是使括号形成元组所必需的,而不仅仅是为了操作顺序)。
递归的情况也需要更复杂一些。两个调用都将返回列表,我们希望合并这些列表。对于第一个递归,我们可以按原样使用返回的列表。对于第二个,我们需要添加
现在的
值到每个元组的开头。我建议使用一个生成器表达式(如果您想将列表与
+
而不是使用
list.extend
).
def powerSum(X, N, current = 1):
pw = pow(current, N)
if pw > X:
return []
elif pw == X:
return [(current,)]
else:
result = powerSum(X, N, current+1)
result.extend((current,) + tup for tup in powerSum(X-pw, N, current+1))
return result
