eHázi q/26594 v2

stairs = (20, 30, 50, 30)
max_step = 100

def main(stairs, max_step):
    known = dict()
    p = possibilities(stairs, max_step, known)
    print(p)

def possibilities(stairs, max_step, known):
    ind = 4- len(stairs)
    if (len(stairs) == 1 and stairs[0] <= max_step) or len(stairs)==0:
        return 1

    p = 0
    for i in range(1,len(stairs)+1):
        down = stairs[:i]
        up= stairs[i:]

        if sum(down) > max_step:
            break
        elif up in known:
            p += known[up]
        else:
            p_up = possibilities(up, max_step, known)
            known[up] = p_up
            p += p_up
    return p

main(stairs, max_step)