forked from TheAlgorithms/Python
-
Notifications
You must be signed in to change notification settings - Fork 0
/
integer_partition.py
37 lines (30 loc) · 1.06 KB
/
integer_partition.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
The number of partitions of a number n into at least k parts equals the number of
partitions into exactly k parts plus the number of partitions into at least k-1 parts.
Subtracting 1 from each part of a partition of n into k parts gives a partition of n-k
into k parts. These two facts together are used for this algorithm.
"""
def partition(m: int) -> int:
memo: list[list[int]] = [[0 for _ in range(m)] for _ in range(m + 1)]
for i in range(m + 1):
memo[i][0] = 1
for n in range(m + 1):
for k in range(1, m):
memo[n][k] += memo[n][k - 1]
if n - k > 0:
memo[n][k] += memo[n - k - 1][k]
return memo[m][m - 1]
if __name__ == "__main__":
import sys
if len(sys.argv) == 1:
try:
n = int(input("Enter a number: ").strip())
print(partition(n))
except ValueError:
print("Please enter a number.")
else:
try:
n = int(sys.argv[1])
print(partition(n))
except ValueError:
print("Please pass a number.")