recursive implementation of sum to target Python

Question

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?

Good observation! target will be swept from range(0,target_max) which could be large, however. — AngusTheMan
– AngusTheMan, Commented Dec 13, 2021 at 23:34
Rather than recursing, there's probably something in itertools that you can use. — Barmar
– Barmar, Commented Dec 13, 2021 at 23:35

Tim Roberts · Accepted Answer · 2021-12-13 23:42:18Z

1

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.

answered Dec 13, 2021 at 23:42

Tim Roberts

55.3k4 gold badges28 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

AngusTheMan Over a year ago

Wow, I have been struggling with that all day! Impressive solution. What does the // do in the range?

Tim Roberts Over a year ago

Integer division. a//b is the same as math.floor(a/b).

Collectives™ on Stack Overflow

recursive implementation of sum to target Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related