Painting Fence Algorithm

Given a number N, the task is to find the number of ways N can be partitioned, i.e. the number of ways that N can be expressed as a sum of positive integers.

Note: N should also be considered itself a way to express it as a sum of positive integers.
Examples:

Input: N = 5
Output: 7
5 can be partitioned in the following ways:
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Input: N = 10
Output: 42

This post has been already discussed in Ways to write n as sum of two or more positive integers. In this post, an efficient approach is discussed.

Approach(Using Euler’s recurrence):
If p(n) is the number of partitions of N, then it can be generated by the following generating function:

Using this formula and Euler’s pentagonal number theorem, we can derive the following recurrence relation for p(n): (Check the Wikipedia article for more details)

where k = 1, -1, 2, -2, 3, -3, … and p(n) = 0 for n < 0.

Below is the implementation of above approach:

Time Complexity: O(N√N)
Space Complexity: O(N)