def getList(n, input_list, caching_list):
函数应该返回一个列表，该列表加起来就是一个数字"0"；n〃；使用inputlist中的数字，假设数字可以重复。希望使用递归。
当前代码：
def getList(n, input_list, caching_list):
if n == 0 :
return caching_list
if n < 0 or len(input_list) == 0:
return []
for i in input_list:
if find_sum(n-i,input_list,caching_list) == caching_list:
caching_list.append(i)
return caching_list
return []
示例n=13，input_list=[2,3,5]应产生[2,2,2,2,3]或[5,5,2]或任何加至13的结果。
只使用一个数字1次很容易做到这一点，但如何考虑多次使用同一数字的情况？
使用递归，这可以使用深度优先搜索(DFS(算法来解决，但它可以抛出RecursionError: maximum recursion depth exceeded in comparison
def find(n2, plist):
result = []
def find2(n):
if n == 0:
return True
if n < 0:
return False
for p in plist:
if find2(n-p):
result.append(p)
return True
find2(n2)
return result
print(find(17, [2,3,5])) # [3, 2, 2, 2, 2, 2, 2, 2]
print(find(7, [3,5])) # []
print(find(77777, [3,5,7,11])) # recursion error
为了消除递归错误，可以将递归DFS重写为迭代DFS。
我发现itertools对于这样的东西非常方便。我相信有更好的方法可以做到这一点，但这可能会让你想要你需要的：
import itertools
def find_sum(n, p_list):
max_len = n // min(p_list)
min_len = n // max(p_list)
for i in range(min_len, max_len+1):
I = itertools.combinations_with_replacement(p_list, i)
for j in I:
if(sum(j) == n):
return(list(j))
return([])
print(find_sum(17,[2,3,5]))
# [2, 5, 5, 5]
print(find_sum(7, [3, 5]))
# []
您可以很容易地更改代码以提供所有组合。
def find_sum(n, p_list):
max_len = n // min(p_list)
min_len = n // max(p_list)
answers = []
for i in range(min_len, max_len+1):
I = itertools.combinations_with_replacement(p_list, i)
for j in I:
if(sum(j) == n):
answers.append(list(j))
return(answers)
find_sum(17,[2,3,5])
#[[2, 5, 5, 5], [2, 2, 3, 5, 5], [3, 3, 3, 3, 5], [2, 2, 2, 3, 3, 5], [2, 3, 3, 3, 3, 3], [2, 2, 2, 2, 2, 2, 5], [2, 2, 2, 2, 3, 3, 3], [2, 2, 2, 2, 2, 2, 2, 3]]
关于@dantebarba的评论，我还没有真正考虑过它将如何应对大问题，而且可能会有更有效的方法。
这3行代码应该会引发一些危险信号：
if find_sum(n-i,p,p_list,sum_list) == sum_list:
sum_list.append(i)
return sum_list
有一个递归函数将其结果存储在sum_list中，对其进行修改，并根据其值进行相等性检查。这使得你的程序很难推理。如果围绕等号交换参数，行为会改变吗？我不知道。
一般来说，递归程序应该尽量避免将结果作为参数传递。既然if语句真的在问我们是否可以求出某个和，为什么不把它分解成一个单独的函数呢？
def can_sum(n, p_list, cache={}):
if n in cache:
return cache[n]
if n == 0:
return True
if n < 0:
return False
return any(can_sum(n-p, p_list) for p in p_list)
您希望使用某种缓存(否则，您的程序是指数时间的(，如果您可以使用外部库，则functools.cache更可取，但这可以完成任务。
find_sum函数应该如何在不将结果作为参数传递的情况下返回结果？只需将您的价值添加到最后，就像您的代码所做的那样：
def find_sum(n, p_list):
for p in p_list:
if can_sum(n-p, p_list):
return find_sum(n-p, p_list) + [p]
return []