algorithm Integer Partition Algorithm Basic Information of Integer Partition Algorithm

Help us to keep this website almost Ad Free! It takes only 10 seconds of your time:
> Step 1: Go view our video on YouTube: EF Core Bulk Insert
> Step 2: And Like the video. BONUS: You can also share it!

Example

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:

  • 5
  • 4 + 1
  • 3 + 2
  • 2 + 2 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1

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.

Equation

Example of Integer Partition Algorithm:

Example of Integer Partition Algorithm

Auxiliary Space: O(n^2)
Time Complexity: O(n(logn))



Got any algorithm Question?