Introduction

Generating the partitions of a number means listing every way to write a positive integer as a sum of positive integers, ignoring order. This is a classic combinatorics problem, and the main implementation challenge is avoiding duplicates such as 3 + 1 and 1 + 3, which represent the same partition.

Define Partitions Carefully

A partition of n is a multiset of positive integers that adds up to n. Order does not matter.

For example, the partitions of 4 are:

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

Notice that 1 + 3 is not a separate partition. That is why a good generator usually builds partitions in nonincreasing order, which prevents reordered duplicates from ever being created.

Use Recursion With a Maximum Allowed Part

A clean recursive strategy is:

• keep track of the remaining sum
• keep track of the largest part you are still allowed to use
• only choose the next part from that limit downward

That naturally preserves nonincreasing order.

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

This prints:

1[5]
2[4, 1]
3[3, 2]
4[3, 1, 1]
5[2, 2, 1]
6[2, 1, 1, 1]
7[1, 1, 1, 1, 1]

Each partition is already in nonincreasing order, so duplicates do not appear.

Why the Maximum-Part Parameter Matters

Without the max_part restriction, the recursion would generate the same partition many times in different orders.

For example, if you simply tried all positive integers that fit into the remainder, you would generate:

• '[3, 1]'
• '[1, 3]'

even though they are the same partition mathematically.

By forcing each next part to be at most the previous part, the generator stays canonical and avoids extra filtering later.

Counting Versus Generating

Sometimes you only need the number of partitions, not the actual list. Counting is a different problem. Generating every partition is inherently expensive because the number of partitions grows quickly as n increases.

That means a generator is appropriate when:

• 'n is modest'
• you truly need each partition
• you want to stream results one by one

The yield-based approach is useful here because it does not need to store all partitions in memory at once.

That lazy behavior is valuable when you only need the first few partitions that satisfy an extra condition. You can iterate until you find what you need and stop immediately, instead of materializing the entire search space in memory first.

Variations You Can Add

Once the basic generator works, it is easy to adapt:

• partitions into distinct parts only
• partitions into odd parts only
• partitions with exactly k parts

The recursive structure stays similar. You simply tighten the rules for what parts are allowed next.

For example, distinct-parts partitions can be generated by requiring the next part to be strictly smaller than the previous one rather than merely less than or equal to it.

Common Pitfalls

• Treating different orders of the same summands as different partitions.
• Building all compositions first and then trying to deduplicate them afterward.
• Forgetting that partition counts grow quickly, so full generation becomes expensive for larger n.
• Returning a huge list when a generator would stream results more efficiently.
• Losing the nonincreasing-order invariant and accidentally reintroducing duplicates.

Summary

• A partition writes n as a sum of positive integers where order does not matter.
• The cleanest generator uses recursion plus a maximum allowed next part.
• Keeping parts in nonincreasing order prevents duplicates naturally.
• A generator is often better than building one giant list because partitions grow quickly.
• Once the basic recursion is clear, it is easy to adapt for distinct, odd, or fixed-length partitions.