Python – Get a combination of numbers where each number is less than a specific number

Given the length k and

target and limit, I want to get a combination of numbers where each number contains [0 ~ limit] and can have k numbers with the sum of target.

So, for example, if I have k=2 target=4 and limit=4,

I will

[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

I tried the above method, but there is no limit to this one.

You’re almost there! You can make very simple modifications to work around that limitation.

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

When we reach the base case of spots == 1, we want to make sure that the remainder is less than the limit. If not, don’t produce anything. Then when we select the numbers we want to combine, do not choose any numbers that exceed the limit!

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