Python一旦找到解决方案就停止递归

Question

我有一个递归函数，目的是在给定整数列表的情况下尝试组成一定的总和。该函数可以工作，但会返回所有可能的解决方案。我想在找到解决方案后跳出递归函数。如何实现呢？以下是该函数的（伪）代码：

function find_sum(list_of_integers, target_sum, partial_solution):
    if partial_solutions == target_sum:
        return True
    if partial_solution > target_sum:
        return

    for i in range(len(list_of_integers)):
        n = list_of_integers[i]
        remaining = list_of_integers[i+1:]
        find_sum(remaining, target_sum, partial_solution + n)

我只想知道这个目标和是否可以由整数列表形成，不需要所有的解决方案。

- Koen

Answer 1

您需要检查递归调用的返回值；如果返回True，立即传播它而不是继续循环：

for i in range(len(list_of_integers)):
    n = list_of_integers[i]
    remaining = list_of_integers[i+1:]
    found = find_sum(remaining, target_sum, partial_solution + n)
    if found:
        return True

- Martijn Pieters

Answer 2

你可以使用这个类。在init方法中初始化变量self.flag=False，当你找到解决方案时，将self.flag改为True，并在self.flag为True时返回None。

class Solution:
    def __init__(self):
        self.flag = False

    def find_sum(....):
        for i in range(len(list_of_integers)):
             if self.flag: return True
             n = list_of_integers[i]
             remaining = list_of_integers[i+1:]
             self.flag = find_sum(remaining, target_sum, partial_solution + n)

    

- Theja M

Answer 3

当你找到解决方案后，只需返回它，并在下一行使用sys.exit(0)，它将停止进一步的递归调用并立即将你退出。

- Prabhjyot Singh