如何在列表中找到所有达到目标值的金额组合？

让我们尝试一下这个（类似于中间相遇算法）：

我们将列表分成两部分，然后为每个部分生成所有可能的总和，包括空的总和。每部分的数量不会超过 32768 个。

然后，对于左边的每个和，我们在右边寻找补数。如果有，那么我们将生成所有组合对。

为了省钱，我们将组合存储为二进制数，其中单个位对应于相应列表中的索引（老实说，这是防止交叉的实验的遗留问题，但我没有重新设计它来存储数字本身）

示例包括捕获长度为 30 的列表中的随机数组合，这会产生相对较长的结果。工作迅速。

对于小目标值的求和问题也可以通过与成比例的时间动态规划来解决target*len(nums))，这里还需要时间来存储和检查难以估计的中间组合，以及target中间组合的空间+存储。

def find_combs(nums: list, target):

    def unzipp(l, r):
        p = []
        t = l | (r<<(len(nums)//2))
        b = 0
        while t:
            if t%2:
                p.append(nums[b])
            t //= 2
            b += 1
        return p

    result = []
    nums = list(set(nums))  # Убираем дубликаты
    n = len(nums)
    left = nums[0:n//2]
    right = nums[n//2:]

    leftdic = {}
    for m in range(1<<len(left)):
        t = m
        s = 0
        b = 0
        while t:
            if t%2:
                s += left[b]
            t //= 2
            b += 1
        if s not in leftdic:
            leftdic[s] = []
        leftdic[s].append(m)
    #print(leftdic)

    rightdic = {}
    for m in range(1<<len(right)):
        t = m
        s = 0
        b = 0
        while t:
            if t%2:
                s += right[b]
            t //= 2
            b += 1
        if s not in rightdic:
            rightdic[s] = []
        rightdic[s].append(m)
    #print(rightdic)

    for k in leftdic.keys():
        t = target - k
        if t in rightdic:
            for l in leftdic[k]:
                for r in rightdic[t]:
                    result.append(unzipp(l,r))

    return result

print(find_combs([2,3,5,7,10,11,13], 21))
print(find_combs([3, 5, 7, 8, 9, 10, 11],25))

import random
a = [random.randint(1,10000000) for i in range(30)]
t = random.randint(1,150000000)
print(a, t)
a = [4687271, 450570, 1115149, 9839847, 7036317, 7247959, 9656662, 5275278, 2884715, 3446792, 1810765, 6462299, 538799, 4396281, 2774047, 4291174, 9304056, 857120, 5572892, 8158331, 1468953, 8955730, 6576077, 2684190, 509857, 6908856, 1566333, 9096332, 6276145, 4670849]
t = 60898739
g = find_combs(a, t)
print(len(g))
for c in g:
    print(c)

 ------

[[10, 11], [3, 7, 11], [3, 5, 13], [2, 3, 5, 11]]
[[5, 9, 11], [3, 5, 8, 9], [7, 8, 10], [3, 5, 7, 10]]

24
[4670849, 3446792, 1115149, 5275278, 6908856, 1810765, 7247959, 6462299, 9839847, 4396281, 8158331, 1566333]
[4670849, 1115149, 5572892, 7036317, 2774047, 857120, 6276145, 6576077, 6462299, 4291174, 9304056, 4396281, 1566333]
[3446792, 7036317, 2684190, 2774047, 857120, 6576077, 8955730, 9656662, 6462299, 4291174, 8158331]
[4670849, 3446792, 1115149, 5275278, 7036317, 2684190, 509857, 6276145, 6576077, 6462299, 4291174, 4396281, 8158331]
[4670849, 450570, 5275278, 2774047, 857120, 509857, 6276145, 6908856, 1810765, 8955730, 7247959, 4291174, 9304056, 1566333]
[4670849, 3446792, 450570, 1468953, 2684190, 2774047, 857120, 509857, 6908856, 1810765, 9656662, 7247959, 4291174, 4396281, 8158331, 1566333]
[3446792, 1115149, 5275278, 1468953, 5572892, 2684190, 2774047, 857120, 509857, 8955730, 9656662, 4291174, 9839847, 2884715, 1566333]
[4670849, 3446792, 450570, 1115149, 5275278, 5572892, 7036317, 2774047, 4687271, 6908856, 9656662, 9304056]
[4670849, 5275278, 5572892, 2684190, 2774047, 857120, 4687271, 6276145, 6908856, 1810765, 9656662, 8158331, 1566333]
[4670849, 3446792, 450570, 5572892, 7036317, 2774047, 509857, 4687271, 6576077, 4291174, 9839847, 2884715, 8158331]
[4670849, 3446792, 450570, 9096332, 1115149, 1468953, 2684190, 2774047, 509857, 4687271, 1810765, 9656662, 4291174, 9839847, 4396281]
[4670849, 450570, 5275278, 7036317, 2684190, 857120, 509857, 4687271, 1810765, 8955730, 9839847, 4396281, 8158331, 1566333]
[4670849, 9096332, 1468953, 5572892, 538799, 6276145, 7247959, 6462299, 9839847, 8158331, 1566333]
[4670849, 450570, 9096332, 1468953, 2774047, 538799, 1810765, 6576077, 9656662, 4291174, 9839847, 8158331, 1566333]
[3446792, 450570, 5275278, 7036317, 2684190, 2774047, 538799, 6276145, 6908856, 8955730, 7247959, 9304056]
[4670849, 3446792, 450570, 9096332, 1115149, 5572892, 2684190, 857120, 538799, 6276145, 1810765, 6576077, 8955730, 2884715, 4396281, 1566333]
[4670849, 450570, 5275278, 1468953, 5572892, 2684190, 2774047, 857120, 538799, 6908856, 7247959, 9839847, 2884715, 8158331, 1566333]
[3446792, 450570, 1115149, 5275278, 1468953, 7036317, 2684190, 2774047, 857120, 538799, 1810765, 7247959, 6462299, 4291174, 2884715, 4396281, 8158331]
[1468953, 7036317, 509857, 538799, 6276145, 1810765, 6576077, 8955730, 7247959, 6462299, 4291174, 8158331, 1566333]
[9096332, 1468953, 7036317, 857120, 4687271, 538799, 6276145, 1810765, 6576077, 8955730, 4291174, 9304056]
[4670849, 450570, 1468953, 2774047, 857120, 4687271, 538799, 6276145, 1810765, 6576077, 7247959, 9839847, 9304056, 4396281]
[5572892, 2684190, 2774047, 857120, 4687271, 538799, 6276145, 6576077, 8955730, 9656662, 6462299, 4291174, 1566333]
[450570, 1115149, 5275278, 1468953, 7036317, 2684190, 2774047, 509857, 4687271, 538799, 1810765, 6576077, 8955730, 4291174, 9839847, 2884715]
[450570, 9096332, 1115149, 5572892, 2684190, 857120, 509857, 4687271, 538799, 6908856, 6576077, 6462299, 2884715, 4396281, 8158331]

因为

1. 我不喜欢我自己对这个问题的其他回答；
2. 我喜欢MBo 的回答中的想法（给他加分）；
3. 并且不喜欢MBo 的答案中的代码（如果还没有，请给他加分）；
4. 我想要优点，

那么我想提供我的解决方案。数字列表被分为两半，具体如何划分并不重要。对于每一半，构建一个字典<sum> → <具有此总和的术语元组列表>。我们查阅第一本字典，在第二本字典中找到了额外的金额。如果找到，我们将打印两个词典中的所有术语组合。速度与激情（就内存而言）：

from itertools import combinations


def sums(nums: list):
    sums = {}
    for r in range(len(nums) + 1):
        for combo in combinations(nums, r):
            sums.setdefault(sum(combo), []).append(combo)
    return sums


def find_combination_7(nums, target):
    d1 = sums(nums[:len(nums) // 2 ])
    d2 = sums(nums[ len(nums) // 2:])

    for k1, v1 in d1.items():
        k2 = target - k1
        v2 = d2.get(k2, [])
        for e2 in v2:
            for e1 in v1:
                yield e1 + e2

对以前的答案进行了小幅改进，或者更确切地说，渐近地进行了显着改进，但对于 Python 而言，改进并不大，因为使用int和相对便宜的操作很昂贵sum()（我对@Stanislav Volodarskiy 的答案大约list有 -20..50％）。find_combination_7()

如果我们按照格雷码的顺序生成组合，那么每个后续组合的和都与前一个组合相差一个元素。

def sums_gray_code(nums: "Sequence[int]") -> dict[int, list[int]]:
    sums = {0: [0]}
    if nums:
        s = nums[0]
        gray = 1
        sums[s] = [gray]
        for term in range((1<<(len(nums) - 1)) - 1):
            idx = (gray&-gray).bit_length()  # Число младших 0-х бит (std::count_zero())
            diff = 1 << idx
            if gray&diff:
                s -= nums[idx]
            else:
                s += nums[idx]
            gray ^= diff
            sums.setdefault(s, []).append(gray)
            if gray&1:
                s -= nums[0]
            else:
                s += nums[0]
            gray ^= 1
            sums.setdefault(s, []).append(gray)
    return sums

def find_combination_gray(nums: "Sequence[int]", target: int) -> "Iterator[int]":
    nums1 = nums[:len(nums) // 2 ]
    nums2 = nums[ len(nums) // 2:]
    d1 = sums_gray_code(nums1)
    d2 = sums_gray_code(nums2)

    for k1, v1 in d1.items():
        k2 = target - k1
        v2 = d2.get(k2, [])
        for e2 in v2:
            for e1 in v1:
                yield (tuple(nums1[i] for i in range(len(nums1)) if e1&(1 << i)) +
                       tuple(nums2[i] for i in range(len(nums2)) if e2&(1 << i)))

测试（不删除重复项）：

def csorted(comb):
    res = [tuple(sorted(c)) for c in comb]
    return sorted(res)

assert csorted(find_combination_gray([1, 1], 2)) == [(1, 1)]
assert csorted(find_combination_gray([1, 2, 1], 2)) == [(1, 1), (2,)]
assert csorted(find_combination_gray([1, 2, 1, 0], 2)) == [
    (0, 1, 1), (0, 2), (1, 1), (2,)
]
assert csorted(find_combination_gray([2,3,5,7,10,11,13], 21)) == [
    (2, 3, 5, 11), (3, 5, 13), (3, 7, 11), (10, 11)
]
assert csorted(find_combination_gray([3, 5, 7, 8, 9, 10, 11],25)) == [
    (3, 5, 7, 10), (3, 5, 8, 9), (5, 9, 11), (7, 8, 10)
]
assert csorted(find_combination_gray([
        4687271, 450570, 1115149, 9839847, 7036317, 7247959, 9656662, 
        5275278, 2884715, 3446792, 1810765, 6462299, 538799, 4396281, 
        2774047, 4291174, 9304056, 857120, 5572892, 8158331, 1468953, 
        8955730, 6576077, 2684190, 509857, 6908856, 1566333, 9096332, 
        6276145, 4670849],60898739)) == [
    (450570, 509857, 538799, 857120, 1115149, 2684190, 2884715, 4396281, 4687271,
     5572892, 6462299, 6576077, 6908856, 8158331, 9096332),
    (450570, 509857, 538799, 1115149, 1468953, 1810765, 2684190, 2774047, 2884715,
     4291174, 4687271, 5275278, 6576077, 7036317, 8955730, 9839847),
    (450570, 509857, 857120, 1468953, 1566333, 1810765, 2684190, 2774047, 3446792,
     4291174, 4396281, 4670849, 6908856, 7247959, 8158331, 9656662),
    (450570, 509857, 857120, 1566333, 1810765, 2684190, 4396281, 4670849, 4687271,
     5275278, 7036317, 8158331, 8955730, 9839847),
    (450570, 509857, 857120, 1566333, 1810765, 2774047, 4291174, 4670849, 5275278,
     6276145, 6908856, 7247959, 8955730, 9304056),
    (450570, 509857, 1115149, 1468953, 1810765, 2684190, 2774047, 3446792, 4291174,
     4396281, 4670849, 4687271, 9096332, 9656662, 9839847),
    (450570, 509857, 2774047, 2884715, 3446792, 4291174, 4670849, 4687271, 5572892,
     6576077, 7036317, 8158331, 9839847),
    (450570, 538799, 857120, 1115149, 1468953, 1810765, 2684190, 2774047, 2884715,
     3446792, 4291174, 4396281, 5275278, 6462299, 7036317, 7247959, 8158331),
    (450570, 538799, 857120, 1115149, 1566333, 1810765, 2684190, 2884715, 3446792,
     4396281, 4670849, 5572892, 6276145, 6576077, 8955730, 9096332),
    (450570, 538799, 857120, 1468953, 1566333, 2684190, 2774047, 2884715, 4670849,
     5275278, 5572892, 6908856, 7247959, 8158331, 9839847),
    (450570, 538799, 857120, 1468953, 1810765, 2774047, 4396281, 4670849, 4687271,
     6276145, 6576077, 7247959, 9304056, 9839847),
    (450570, 538799, 1468953, 1566333, 1810765, 2774047, 4291174, 4670849, 6576077,
     8158331, 9096332, 9656662, 9839847),
    (450570, 538799, 2684190, 2774047, 3446792, 5275278, 6276145, 6908856, 7036317,
     7247959, 8955730, 9304056),
    (450570, 1115149, 2774047, 3446792, 4670849, 4687271, 5275278, 5572892,
     6908856, 7036317, 9304056, 9656662),
    (509857, 538799, 1468953, 1566333, 1810765, 4291174, 6276145, 6462299, 6576077,
     7036317, 7247959, 8158331, 8955730),
    (509857, 857120, 1115149, 1468953, 1566333, 2684190, 2774047, 2884715, 3446792,
     4291174, 5275278, 5572892, 8955730, 9656662, 9839847),
    (509857, 1115149, 2684190, 3446792, 4291174, 4396281, 4670849, 5275278,
     6276145, 6462299, 6576077, 7036317, 8158331),
    (538799, 857120, 1468953, 1810765, 4291174, 4687271, 6276145, 6576077, 7036317,
     8955730, 9096332, 9304056),
    (538799, 857120, 1566333, 2684190, 2774047, 4291174, 4687271, 5572892, 6276145,
     6462299, 6576077, 8955730, 9656662),
    (538799, 1468953, 1566333, 4670849, 5572892, 6276145, 6462299, 7247959,
     8158331, 9096332, 9839847),
    (857120, 1115149, 1566333, 2774047, 4291174, 4396281, 4670849, 5572892,
     6276145, 6462299, 6576077, 7036317, 9304056),
    (857120, 1566333, 1810765, 2684190, 2774047, 4670849, 4687271, 5275278,
     5572892, 6276145, 6908856, 8158331, 9656662),
    (857120, 2684190, 2774047, 3446792, 4291174, 6462299, 6576077, 7036317,
     8158331, 8955730, 9656662),
    (1115149, 1566333, 1810765, 3446792, 4396281, 4670849, 5275278, 6462299,
     6908856, 7247959, 8158331, 9839847)
]

注意：如果您想使用此解决方案，请先阅读最后一节。

错误

无法删除重复项。该调用find_combination_2([1, 1], 2)必须返回一个解决方案。如果删除重复项，那么根本就没有解决方案。另一方面，如果调用find_combination_2([1, 1, 1], 1)返回三个相同的解决方案（来自的三个不同的单位），那就不好了nums。所以我认为应该删除重复的解决方案（而不是原始数字）。

您的函数未找到所有组合。一切都是因为break结局。对于nums = [1, 2, 3, 4, 5]和，target = 5它将返回两种组合：[5]，[1, 4]。如果删除break，将会发现另一个答案：[2, 3]。

表现

我测试了没有的选项break。在示例中nums = list(range(1, n + 1))，target = n。数字没有重复，第一个缺失并不影响答案。

n = int(input())
nums = list(range(1, n + 1))
target = n
for r in find_combination_2(nums, target):
    print(r)

每增加n一个单位，操作时间就会增加约两倍。如果您理解要整理2n^个项的组合，那么这是很自然的。对于n = 30，我的计算机花了一分四十秒来找到答案。

搜索可能会花费很长时间。在当前的设计中，用户直到整个搜索完成才会看到结果。你坐在屏幕前，不知道还要等多久。将函数转换为生成器将减轻这个缺点：用户将在解决方案可用时立即获得解决方案。

递归和搜索：

def find_combination_3(nums, target):
    expr = []

    def search(i, s):
        if i == len(nums):
            if s == target:
                yield expr
        else:
            expr.append(nums[i])
            yield from search(i + 1, s + nums[i])
            expr.pop()
            yield from search(i + 1, s)

    return search(0, 0)

此函数在三分五十秒内找出三十个术语的所有组合。这意味着它花费230秒完成你的函数在100秒内完成的工作。这是一种优化。

但是此代码可以进行优化：我们将检查当前总数尚未超过目标总数，以及剩余项是否足以达到目标总数：

def find_combination_4(nums, target):
    expr = []

    def search(i, low, high):
        if not low <= target <= high:
            return
        if i == len(nums):
            assert low == high
            yield expr
        else:
            expr.append(nums[i])
            yield from search(i + 1, low + nums[i], high          )
            expr.pop()
            yield from search(i + 1, low          , high - nums[i])

    return search(0, 0, sum(nums))

并且该函数可以在大约0.01秒内找到所有组合，也就是说，比不使用不等式检查的搜索快一万倍。

但这还不是极限。重点在于，条件搜索的速度受 中术语的顺序影响nums。先处理大额条款会更有利可图。然后条件将尽早切断不成功的和：

def find_combination_5(nums, target):
    nums = sorted(nums, reverse=True)
    expr = []

    def search(i, low, high):
        if not low <= target <= high:
            return
        if i == len(nums):
            assert low == high
            yield expr
        else:
            expr.append(nums[i])
            yield from search(i + 1, low + nums[i], high          )
            expr.pop()
            yield from search(i + 1, low          , high - nums[i])

    return search(0, 0, sum(nums))

在这种形式下，函数可以以十倍的速度完成所有答案：仅用0.001秒。

我将添加一个选项，在我看来，它可以正确处理重复的术语。原则上，它们都是一样的：使用切分进行递归搜索，但术语是预先分组的：

import collections


def find_combination_6(nums, target):
    pairs = sorted(collections.Counter(nums).items(), reverse=True)
    expr = []

    def search(i, low, high):
        if not low <= target <= high:
            return
        if i == len(pairs):
            assert low == high
            yield expr
        else:
            a, k = pairs[i]
            high -= a * k
            yield from search(i + 1, low, high)
            for _ in range(k):
                expr.append(a)
                low += a
                high += a
                yield from search(i + 1, low, high)
            del expr[-k:]

    return search(0, 0, sum(a * k for a, k in pairs))

自我批评

我选择用来展示递归修剪搜索的好处的例子很好地说明了它的好处：“加速一万倍”听起来不错。下面是另一个例子，表明有时所有的加速度都不值得：

    n = int(input())
    nums = list(range(1001, 1001 + n))
    target = 500 * n
    for r in find_combination_6(nums, target):
        print(r)

在这个例子中，大多数优化都变成了失败。两分钟讲三十个词。我们又回到了原点，甚至更加糟糕。经验是艰难错误之子。