递归:查找所有在列表中添加元素以得到n的方法

Question

例如

given a list [1,2,3,4] and `n=4`

我的输出应该是

7:
1+1+1+1=4
1+1+2=4
1+2+1=4
1+3=4
2+2=4
2+1+1=4
3+1=4

我正在与递归方面作斗争，希望在思考过程和代码方面得到一些帮助。

我知道我需要找到一个基本情况，但我找不到这个问题的基本情况。我认为如果lst=[]且n==0，则返回0 '。不确定这是否适用于基本情况，但如果适用，我该如何继续呢?

Answer 1

我的建议是将结果的递归性质与结果的格式化分开。也就是说，我不会同时递归和构造字符串:

def equations(numbers, target):
def equations_recursive(numbers, target):
solutions = []
for number in numbers:
if number < target:
sub_solutions = equations_recursive(numbers, target - number)
for sub_solution in sub_solutions:
if number + sum(sub_solution) == target:
solutions.append([number, *sub_solution])
elif number == target:
solutions.append([number])
return solutions
solutions = equations_recursive(numbers, target)
return ["{}={}".format('+'.join(map(str, s)), target) for s in solutions if len(s) > 1]
print(*equations([1, 2, 3, 4], 4), sep='n')

内部equations_recursive()函数调用的结果是:

[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]

外部equations()函数的最后一行对结果进行过滤和格式化:

> python3 test.py
1+1+1+1=4
1+1+2=4
1+2+1=4
1+3=4
2+1+1=4
2+2=4
3+1=4
>

Answer 2

我是这样做的。这不是最有效的方法，但是有效!:

def recursion_list1(numbers, target_num, lst):
recursion_list2(numbers * target_num, target_num, lst)
def recursion_list2(numbers, target_num, all_lst, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target_num:
if len(partial) >= 2 and partial not in all_lst:
part = " + ".join([str(a) for a in partial])
all_lst.append(partial)
print(f"{part} = {target_num}")
elif s >= target_num:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i + 1:]
recursion_list2(remaining, target_num, all_lst, partial + [n])

if __name__ == "__main__":
lst = []
recursion_list1([1,2,3,4], 4, lst)

让我解释一下:

首先，我们创建一个小函数，它只做一件事。它乘以列表使它变大，如果这样说得通的话。基本上，没有它，我们有一个[1, 2, 3, 4]的名单。因此，加起来等于4的数字组合只有1, 3和4。然而，当我们将列表乘以目标数时，我们得到一个[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]的列表。因此，我们可以访问更多的组合，如1, 1, 1, 1。您可以去掉第一个函数，而是将脚本中的最后一行改为recursion_list1([1,2,3,4] * 4, 4, lst)。注意我添加的* 4.

接下来，我们创建第二个main函数。首先，获取新列表的和，偏值。然后，我们看看和是否等于目标数。如果是，那么我们再运行几个If语句。第一部分检查列表中的和是否大于1位。这是因为，如果我们不这样做，我们将得到4 = 4作为结果之一，其中没有加法。if语句的下一部分检查组合是否已经在一个名为all_list的列表中。这是至关重要的，因为它将帮助我们过滤掉任何重复。

现在，如果所有这些if语句都返回true，则输出组合并将其添加到列表all_list中。因此，如果下一次迭代返回与第一次相同的结果，则它不会输出它，因为结果已经在主列表中了。

如果列表的和大于数字，则停止列表，因为继续没有意义。

最后，创建一个for循环，以便循环遍历列表中的所有值。for循环是这样工作的:

假设我们得到一个[1, 2, 3, 4]的列表，在第一个函数之后，它将是[1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]。第一个for循环遍历所有值:1、2、3、4。然而，它也再次运行函数，这意味着for循环也再次运行，这次循环遍历第二个值。因此，我们得到1,1然后1,2然后1,3然后1,4，然后1,1，然后1,2…最后，2,1和2,2…等等，如果你觉得有意义的话。