sum到目标Python的递归实现

Question

我有以下方法，在给定目标整数的情况下，生成从有序整数行创建整数的所有方法，但条件是列索引(从1开始)乘以对每一行目标的数字和。

下面是一些实现这一目标的代码。

target = 7
for x in range(math.floor(target/4)+1):
    for f in range(math.floor((target-4)/3)+1):
        for t in range(math.floor((target-4*x-3*f)/2)+1):
            s = target - 2*t - 3*f - 4*x
            print(s,t,f,x)

7 0 0 0
5 1 0 0
3 2 0 0
1 3 0 0
4 0 1 0
2 1 1 0
0 2 1 0
3 0 0 1
1 1 0 1
0 0 1 1

注意，所有行之和为target=7，即取底部行0*1 + 0*2 + 1*3 + 1*4=7。

在一般情况下，我不知道我需要的列数。例如，我可能只是

target = 7
for t in range(math.floor(target/2)+1):
    s = target - 2*t
    print(s,t)

或者更多的for循环。

我如何概括这一点，很可能是基于递归解决方案，以便列数是一个参数？

Answer 1

这里有一个递归的解决方案。您只需遍历最后一列的选项，然后使用其余的列获取任何剩馀部分的组合。

def gencombos( target, column ):
    if column == 1:
        yield [target]
    else:
        for i in range( 0, target//column+1 ):
            for row in gencombos( target-i*column, column-1 ):
                yield row+[i]

for row in gencombos( 7, 4 ):
    print(row)

输出：

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

您可以将调用更改为(7,6)以查看差异。