Basic Information of Integer Partition Algorithm

suggest change

The partition of an integer is a way of writing it as a sum of positive integers. For example, the partitions of the number 5 are:

Notice that changing the order of the summands will not create a different partition.

The partition function is inherently recursive in nature since the results of smaller numbers appear as components in the result of a larger number. Let p(n,m) be the number of partitions of n using only positive integers that are less than or equal to m. It may be seen that p(n) = p(n,n), and also p(n,m) = p(n,n) = p(n) for m > n.

Example of Integer Partition Algorithm:

Auxiliary Space: O(n^2)

Time Complexity: O(n(logn))

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:



Table Of Contents