有没有办法递归地找到一组数字可以加起来达到某个数字的不同方式?

Question

我希望能够找到一组数字(x(可以求和为某个值的所有不同方式，y，但我甚至很难正确获得基本情况。

例如：

如果我有 x = set (1,2,3,4,5(，我想看看有多少种不同的方式 y = 5 可以用 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