recursive implementation of sum to target Python-CodePudding

I have the following method that, given a target integer, generates all ways to create that integer from an ordered row of integers, subject to the condition that the column index (starting from one) multiplied by the number sums to the target for each row.

Below is some code that achieves this.

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

Notice that all rows sum to target=7, i.e. take the bottom row 0*1 0*2 1*3 1*4=7.

In the general case, I do not know the number of columns that I require. For instance, I might simply have

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

or indeed, many more for loops.

How can I generalise this, most likely based on a recursive solution, so that the number of columns is a parameter?

CodePudding user response：

Here is a recursive solution. You just run through the options for the last column, then fetch the combinations for whatever's leftover using the remaining columns.

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)

Output:

[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]

You can change it the call to (7,6) to see the difference.