python - 获取每个数字小于某个数字的数字组合

Question

给定长度k和target，limit我想得到一个数字组合，其中每个数字包含[0 ~ limit]并且可以有k数字并且总和为target。

因此，例如，如果我有k=2 target=4and limit=4，

我会有

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

def get_combination(spots, target):
    if spots == 1:
        yield (target, )
    else:
        for i in range(target + 1):
            for j in get_combination(spots - 1, target - i):
                yield (i, ) + j

我试过上面的方法，但是这个没有限制。

标签： python

Answer 1

您快到了！您可以进行非常简单的修改来解决限制。

def get_combination(spots, target, limit):
    if spots == 1 and target <= limit:
        yield (target, )
    elif spots > 1:
        for i in range(limit + 1):
            for j in get_combination(spots - 1, target - i, limit):
                yield (i, ) + j

当我们到达 的基本情况时spots == 1，我们希望确保余数小于限制。如果不是，不要产生任何东西。然后当我们选择数字进入组合时，不要选择超过限制的任何东西！

>>> list(get_combination(2,4,3))
[(1, 3), (2, 2), (3, 1)]