Partition function

Count the number of ways to partition a positive integer into positive integers.

math recursion memoization integers

In number theory, the partition function p(n) counts the number of distinct ways to write a positive integer n as a sum of positive integers, where order does not matter. For example, the integer 4 can be expressed in 5 ways: 4, 3+1, 2+2, 2+1+1, 1+1+1+1. For n = 0 we define p(0) = 1 (the empty sum). Implement a function `partition(n)` that takes a non-negative integer `n` and returns the integer p(n). Your solution must handle values up to n = 200 efficiently (within reasonable time). Use any algorithm you like, but avoid exponential runtime.

Constraints

0 <= n <= 200. The answer fits within a standard Python integer (unbounded). Your function should complete within 2 seconds.

Example

>>> partition(4)
5
>>> partition(5)
7
>>> partition(6)
11
>>> partition(0)
1
>>> partition(1)
1

12 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Consider a recursive formula that subtracts a part from n and ensures non-increasing order to avoid duplicates.

Use memoization (e.g., lru_cache or a dictionary) to avoid recomputing the same subproblems.

A common recursion is p(n, k) = p(n, k-1) + p(n-k, k) where k is the maximum allowed part.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.