Python2.7在列表中查找添加到另一个numb的数字组合

Question

我要做的是找到一种方法，让我的代码返回从一个添加到变量的列表中的所有值的组合，以列表的形式返回每个答案。例如

    target_number = 8
    usingnumbers =  [1, 2, 4, 8]
    returns:
    [8]
    [4, 4]
    [4, 2, 2]
    [4, 2, 1, 1]
    [4, 1, 1, 1, 1]
    [2, 2, 1, 1, 1, 1]
    [2, 1, 1, 1, 1, 1, 1]
    [1, 1, 1, 1, 1, 1, 1, 1]

等等。我希望重复的值被丢弃，例如[4，2，2]，[2，4，2]，[2，2，4]在技术上都是有效的，但我只想显示其中一个。理想情况下，我希望代码也返回每个数字在每个列表中出现的次数，但我相信我自己可以做到这一点。在

Answer 1

在psuedocode中：

1. 从你写的单子数的最大数开始，保持你的轨道数
2. 一直循环到你再也不能了
3. 转到第二大等等
4. 再次开始这个循环，但是从比上一个循环小的数字开始。在

没那么难。在

Answer 2

不打算为您编写代码，但主要思想是：

函数F(n, (k1, k2, .. km))-返回一组数字列表：

{(a11, ... a1i), (a21, ... a2i), ... (aj1, ... aji )}

有反复关系：

F(n, (k1, k2, .., km)) = union(
  (k1) (+) F(n - k1, (k1, k2, ... km)),
  (k2) (+) F(n - k2, (k2, k3, ... km)),
  ...
  (km) (+) F(n - km, (km))
)

操作a (+) b是“将a附加到b的每一项”。在

有一些小案件，但这取决于你。在

Answer 3

这是问题的一个完整的解决方案，整个函数是一个伪装的大生成器，第一个for循环使用最小的硬币，在第二个循环中，最小的硬币被丢弃，下一个大的硬币将成为我们递归函数的基础。如果列表中的硬币数量大于当前列表中的总和，则将其返回给当前列表。在

def changes(number, coins_available, coins_current):
    if sum(coins_current) == number:
        yield coins_current
    elif sum(coins_current) > number:
        pass
    elif coins_available == []:
        pass
    else:
        for c in changes(number, coins_available[:], coins_current + [coins_available[0]]):
            yield c
        for c in changes(number, coins_available[1:], coins_current):
            yield c

n = 40
coins = [1,2,5,10,20,50,100]

solutions = [sol for sol in changes(n, coins, [])]

for sol in solutions:
    print sol

print 'least coins used solution:', min(solutions, key=len)
print 'number of solutions', len(solutions)