Introduction

Partitioning an integer into sums and partitioning an integer into products are related ideas, but they are not the same problem. Additive partitions ask how a number can be written as a sum of positive integers when order does not matter, while multiplicative partitions ask how it can be written as a product of integers greater than 1, again ignoring order.

Additive Partitions

For additive partitions, order is irrelevant. The number 5 has these partitions:

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

A recursive way to generate them is to keep the next part no larger than the previous one. That guarantees combinations are produced once instead of in many reordered forms.

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

The max_part argument enforces non-increasing order, which is the key to avoiding duplicates.

Multiplicative Partitions

Multiplicative partitions work similarly in spirit, but the recursion uses divisors rather than candidate addends. For 12, the multiplicative partitions are:

• '12'
• '6 × 2'
• '4 × 3'
• '3 × 2 × 2'

Again, order does not matter, so 2 × 6 is the same as 6 × 2.

1import math
2
3
4def multiplicative_partitions(n, min_factor=2):
5    yield [n]
6    for factor in range(min_factor, int(math.sqrt(n)) + 1):
7        if n % factor == 0:
8            for rest in multiplicative_partitions(n // factor, factor):
9                yield [factor] + rest
10
11
12for p in multiplicative_partitions(12):
13    print(p)

The min_factor parameter plays the same role as max_part in the additive case: it prevents duplicates caused by reordering.

Why These Problems Feel Similar

Both problems are recursive decompositions of an integer under an order-insensitive rule. In both cases, the important trick is to impose an ordering constraint so that each partition is generated once.

But their mathematical behavior is different.

For additive partitions, every positive integer has many possible decompositions, and the number of partitions grows rapidly. For multiplicative partitions, the prime factorization of the number strongly constrains the possibilities. Prime numbers, for example, have only the trivial multiplicative partition consisting of the number itself.

Dynamic Programming for Counting Additive Partitions

If you only need the number of additive partitions, not the full list, dynamic programming is usually better than generating every partition.

1def count_additive_partitions(n):
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_additive_partitions(5))

This works because each part size is introduced in increasing order, preventing permutation duplicates automatically.

When Sums and Products Meet in the Same Question

Sometimes the phrase “partition into sums and products” means a hybrid puzzle, such as finding expressions where grouped sums are multiplied, or comparing additive and multiplicative decompositions of the same integer. In those cases, the exact problem statement matters a lot.

For example, these are very different tasks:

• list all additive partitions of n
• list all multiplicative partitions of n
• find a partition of n whose product is maximal
• split n into terms that satisfy both sum and product constraints

The algorithms differ once the question becomes optimization instead of enumeration.

Complexity and Practical Limits

Enumerating all partitions grows expensive quickly. Even when the recursive generator is elegant, the output size itself becomes large. That means no algorithm can list all partitions quickly for large n because the answer contains too many objects.

In practice:

• use recursion when you need the actual partitions for small or moderate n
• use dynamic programming when you only need counts
• use divisor-based recursion for multiplicative partitions

Choosing the wrong approach usually means generating far more structure than the program really needs.

Common Pitfalls

A common mistake is forgetting that order does not matter. Without an ordering constraint, recursive code will generate duplicates such as [3, 2] and [2, 3].

Another mistake is allowing 1 as a multiplicative factor repeatedly. That creates endless trivial decompositions, so multiplicative partitions usually restrict factors to values greater than 1.

Developers also confuse counting partitions with listing them. Counting can often be done with dynamic programming, while listing necessarily scales with the size of the output.

Finally, make sure the problem statement is specific about whether the trivial partition containing only n should be included.

Summary

• Additive partitions decompose an integer into sums, ignoring order.
• Multiplicative partitions decompose an integer into factors greater than 1, also ignoring order.
• Recursive generation works well when you enforce an ordering rule to avoid duplicates.
• Dynamic programming is often better when you only need counts for additive partitions.
• Hybrid “sum and product” questions need a precise statement because the algorithm depends on the exact constraint.