Есть ли способ рекурсивно найти различные способы суммирования набора чисел до определенного числа?

Question

Я хочу найти все возможные способы суммирования набора чисел (x) в определенное значение y, но у меня проблемы даже с базовым случаем.

Например:

Если у меня x = set (1,2,3,4,5) и я хочу посмотреть, сколько разных способов y = 5 можно суммировать с помощью чисел from x:

моя рекурсивная функция вернет 7, потому что:

'''
5
4+1 
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
'''
def recur(x,y):
    if y == x:
        v += 1
    if y > x:
        v += 0
    else: 
         #call recursively

Answer 1

Это не использует рекурсию, но itertools.combinations_with_replacement:

def all_combs(y, x=range(1, 5+1)):
    all_combs = []
    for i in range(1, y+1):
        combs = combinations_with_replacement(x, i)
        all_combs.extend([comb for comb in combs if sum(comb) == y])
    return all_combs

combs = all_combs(5)
# [(5,), (1, 4), (2, 3), (1, 1, 3), (1, 2, 2), (1, 1, 1, 2), (1, 1, 1, 1, 1)]
num_combs = len(combs) # 7