Introduction

Integer partitioning asks for all ways to write a positive integer as a sum of positive integers, ignoring order. In Python, the most elegant solutions are usually recursive generators for listing partitions and memoized recursion or dynamic programming for counting them.

What "Partition" Means

The partitions of 4 are:

• '4'
• '3 + 1'
• '2 + 2'
• '2 + 1 + 1'
• '1 + 1 + 1 + 1'

Notice that 3 + 1 and 1 + 3 count as the same partition. That is the key constraint. A clean algorithm should avoid generating duplicate reorderings.

A Generator That Yields Partitions

A readable Python approach is to generate partitions in non-increasing order. That prevents duplicates naturally.

1def partitions(n: int, max_part: int | None = None):
2    if n == 0:
3        yield []
4        return
5
6    if max_part is None or max_part > n:
7        max_part = n
8
9    for part in range(max_part, 0, -1):
10        for rest in partitions(n - part, part):
11            yield [part] + rest
12
13
14for p in partitions(5):
15    print(p)

Why this works:

• 'part picks the next value in the sum'
• recursive calls reduce the remaining total
• the next part is limited to part, so the sequence never increases

That ordering rule is what removes duplicates elegantly.

Count Partitions Efficiently

If you only need the number of partitions, generating every partition is unnecessary. Counting with memoization is much faster.

1from functools import lru_cache
2
3
4@lru_cache(maxsize=None)
5def partition_count(n: int, max_part: int) -> int:
6    if n == 0:
7        return 1
8    if n < 0 or max_part == 0:
9        return 0
10
11    return (
12        partition_count(n - max_part, max_part) +
13        partition_count(n, max_part - 1)
14    )
15
16
17def count_partitions(n: int) -> int:
18    return partition_count(n, n)
19
20
21print(count_partitions(5))  # 7

This version uses the classic include-or-exclude recurrence:

• include max_part
• or skip it and try smaller parts

Memoization turns repeated subproblems into cache hits.

Dynamic Programming Alternative

If you prefer iterative code, dynamic programming is also clean.

1def count_partitions_dp(n: int) -> int:
2    dp = [0] * (n + 1)
3    dp[0] = 1
4
5    for part in range(1, n + 1):
6        for total in range(part, n + 1):
7            dp[total] += dp[total - part]
8
9    return dp[n]
10
11
12print(count_partitions_dp(5))  # 7

This is similar in spirit to coin-change counting. Each part contributes to higher totals without counting different orders separately.

For counting only, this approach is compact and efficient.

Choose the Right Version for the Job

Use the generator when you need to inspect or print actual partitions.

Use memoized counting or DP when you only need totals, for example:

• combinatorics experiments
• contest problems
• mathematical analysis

Generating all partitions gets expensive quickly because the number of partitions grows fast. Elegant code should still respect the size of the output.

Formatting the Output

If you want partitions printed in a human-friendly form:

for p in partitions(6):
    print(" + ".join(map(str, p)))

That keeps the generator generic while formatting stays outside the algorithm.

This separation is useful because:

• the same generator can feed tests
• callers can convert lists into tuples or strings
• algorithm logic stays independent of presentation

Common Pitfalls

• Generating permutations of the same partition instead of canonical partitions.
• Using recursion without a max-part constraint and producing duplicates.
• Generating all partitions when only the count is needed.
• Forgetting that partition counts grow quickly and can become expensive.
• Mixing formatting logic directly into the recursive core.

Summary

• A clean partition generator keeps parts in non-increasing order to avoid duplicates.
• Memoized recursion is elegant for counting partitions.
• Dynamic programming is a strong iterative alternative when only counts matter.
• Separate partition generation from output formatting.
• Pick the algorithm based on whether you need actual partitions or just the total count.