Using recursion to count methods to divide an integer with certain nums-CodePudding

I've been trying to find how many different methods are there to divide certain integer into a sum of certain numbers. But I fail to solve it.

The original question is :

Suppose that short bars of lengths 5 cm, 8 cm, 17 cm, and 28 cm need to be cut from a very long bar.
Write a recursive function that calculates the number of different ways to cut the above short bars from a bar of length n cm, with no more than 3cm of the bar being wasted.

So that is, using [5, 8, 17, 18] to divide a certain integer

def cut(x):
    m = 0
    l = [5, 8, 17, 28]
    def cut_rod(x, m):
        if x <= 3:
            return m
        else:            
             # I don't know what can I do here
                return cut_rod(x, m 1)
    return cut_rod(x, m)
        
for i in range(int(input())):
    print(cut(int(input( )))

eg.input
line1: amount of bars = 3, then input for 3 times line2 to the bottom: length of each bar (int)

eg.output 3 bars input, so output 3 lines 71 means there are 71 different ways to divide bar1 which length is 100

71
229
667

CodePudding user response：

Well, one recursive approach that produces your results:

def cut(x):
    l = [5, 8, 17, 28]
    def cut_rod(x, pool):
        if x < 0:  # base case 1: you cut more than there was available
            return 0
        if x <= 3: # base case 2: success, legal rest, no more cuts
            return 1
        # recursion:cut off each length, then work with the remainder
        # restriction: to avoid duplicates, you cannot cut shorter ones than before
        result = 0
        for i, v in enumerate(pool):
            result  = cut_rod(x-v, pool[i:])
        return result
    return cut_rod(x, l)

cut(100)
# 71
cut(160)
# 229
cut(240)
# 667

Bonus:

That logic can be condensed:

def cut(x):
    def rec(x, p):
        return x >= 0 and (x <= 3 or sum(rec(x-v, p[i:]) for i, v in enumerate(p)))
    return cut_rod(x, [5, 8, 17, 28])