python - 查找总和为给定数字的值组合的函数

Question

帖子Finding Combinations to the provided Sum value介绍了功能subsets_with_sum()。它在总和等于给定值的数组中找到值的组合。但是由于该职位已有6年以上的历史，所以我发了一个帖子问：此功能如何工作？到底在做什么

def subsets_with_sum(lst, target, with_replacement=False):
    x = 0 if with_replacement else 1
    def _a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u + x, l + [lst[u]], r, t)
        return r
    return _a(0, [], [], target)

Answer 1

首先，我将添加一些换行符以使其更易于阅读：

def subsets_with_sum(lst, target, with_replacement=False):
    x = 0 if with_replacement else 1
    def _a(idx, l, r, t):
        if t == sum(l): 
            r.append(l)
        elif t < sum(l): 
            return
        for u in range(idx, len(lst)):
            _a(u + x, l + [lst[u]], r, t)
        return r
    return _a(0, [], [], target)

您会注意到的第一件事是 subsets_with_sum定义了一个函数，并在最后一个 return语句中对其调用了一次。第一个元素是从中对值进行采样的列表，第二个元素是目标总和，第三个是参数，该参数告诉函数 lst中的单个元素是否可以多次使用。

因为 _a是在 subsets_with_sum中定义的，所以它用传递给 subsets_with_sum的值括起来-这很重要，对于 lst的每个递归调用， _a都是相同的。注意的第二件事是 l是值列表，而 r是列表列表。重要的是，对于每个 l调用， _a是一个不同的对象（这是由于 l + [lst[u]]导致与 l串联的 [lst[u]]副本）。但是， r表示每个 _a调用相同的对象- r.append(l)对其进行适当修改。

我将从 with_replacement == True开始，因为我发现它更简单。第一次调用时， _a被传递 0, [], [], target。然后，它检查是否 t == sum(l)并将其附加到 r，因此 r的唯一元素将是总计为 t（或 target）的列表。如果 sum(l)，则通过返回 None丢弃该递归分支。如果 l元素的总和小于 target，则对于 lst中的每个元素，该元素将附加到 l的副本中，并使用该列表调用 _a。这是该功能的修订版，可以打印出步骤，因此我们可以检查会发生什么：

def subsets_with_sum(lst, target, with_replacement=False):
    x = 0 if with_replacement else 1
    def _a(idx, l, r, t, c):
        if t == sum(l): 
            r.append(l)
        elif t < sum(l): 
            return
        for u in range(idx, len(lst)):
            print("{}. l = {} and l + [lst[u]] = {}".format(c, l, l + [lst[u]]))
            _a(u + x, l + [lst[u]], r, t, c+1)
        return r
    return _a(0, [], [], target, 0)

调用 subsets_with_sum([1,2,3], 2, True)，将打印以下内容（我对打印行进行了重新排序和分隔，以便于阅读）：

0. l = [] and l + [lst[u]] = [1]
0. l = [] and l + [lst[u]] = [2]
0. l = [] and l + [lst[u]] = [3]

1. l = [1] and l + [lst[u]] = [1, 1]
1. l = [2] and l + [lst[u]] = [2, 2]
1. l = [2] and l + [lst[u]] = [2, 3]
1. l = [1] and l + [lst[u]] = [1, 2]
1. l = [1] and l + [lst[u]] = [1, 3]

2. l = [1, 1] and l + [lst[u]] = [1, 1, 1]
2. l = [1, 1] and l + [lst[u]] = [1, 1, 2]
2. l = [1, 1] and l + [lst[u]] = [1, 1, 3]

您可以看到级别为 l + [lst[u]]的右列（ c）等于级别为 l的左列（ c + 1）。此外，请注意 [3]- c == 0不会超过 elif t < sum(l)的最后一行，因此不会被打印。同样，位于 [2]的 c == 1附加到 r，但是分支继续进行到下一级，因为 lst的一个或多个元素可能等于0，因此将它们附加到 [2]导致另一个列表的总和为 target。

另外，请注意，对于某个特定级别 c的每个列表，其最后一个元素为 lst[u]会在下一个级别 len(lst) - u出现 c + 1-次，因为这是每个 lst[z]的列表组合数>，其中 z >= u。

那么 with_replacement == False会发生什么（默认情况）？好吧，在这种情况下，每次将 lst[u]添加到 l和 sum(l) < t，以便 l的特定实例继续到下一个递归级别，只有 lst[z]可以添加到列表中，其中 ，因为 z > u被传递到相应的 u + 1调用。让我们看看调用 _a时会发生什么：

0. l = [] and l + [lst[u]] = [1]
0. l = [] and l + [lst[u]] = [3]
0. l = [] and l + [lst[u]] = [2]

1. l = [1] and l + [lst[u]] = [1, 1]
1. l = [1] and l + [lst[u]] = [1, 2]
1. l = [1] and l + [lst[u]] = [1, 3]
1. l = [2] and l + [lst[u]] = [2, 2]
1. l = [2] and l + [lst[u]] = [2, 3]

2. l = [1, 1] and l + [lst[u]] = [1, 1, 1]
2. l = [1, 1] and l + [lst[u]] = [1, 1, 2]
2. l = [1, 1] and l + [lst[u]] = [1, 1, 3]

现在观察到，对于某个特定级别 subsets_with_sum([1,2,3], 2, False)的每个列表，其最后一个元素为 c会在下一个级别 lst[u]出现 len(lst) - u - 1倍，因为这是每个 c + 1的列表组合数，其中 lst[z]。将此与上面分析的 z > u进行比较。

我建议您更多地使用它，直到您对它有所了解为止。不管替换如何，重要的是要意识到return语句总是返回给调用者。 with_replacement=True的第一次调用返回到 _a，然后该 subsets_with_sum返回到调用方（可能是您或其他函数）。对 _a的所有其他（递归）调用返回到 _a调用的先前实例，这些实例只是丢弃返回的值（或更准确地说，不必理会它）。之所以选择正确的 r是因为它的行为有点像全局值-每个找到解决方案的 _a调用都将其添加到相同的 r中。

最后， subsets_with_sum不能完全按照我期望的功能运行。尝试以下两个调用： subsets_with_sum([2,2,1], 5, True)和 subsets_with_sum([2,2,1,1,1], 5, False)。