76. Counting summations.md

76. Counting summations

Question

It is possible to write five as a sum in exactly six different ways:

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

Solution

Some practice on Leetcode helps me solve this problem within five minutes xD

def p76(N=100):
    @lru_cache(maxsize=None)
    def f(n, i=1):
        """i: min integer can be used to form the sum"""
        if n == 0: return 1
        if n < i: return 0
        res = 0
        for j in range(i, n + 1):
            res += f(n - j, j)
        return res

    return f(N) - 1  # exclude N is written as N

Answer

190569291