Introduction

Generating all partitions of a set means listing every way to split the elements into non-empty, disjoint blocks. It is a classic combinatorics problem, and the standard practical solution is recursive backtracking that builds partitions one element at a time.

What a Set Partition Looks Like

For the set 1, 2, 3, the partitions are:

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

Each partition groups every element exactly once, and no block is empty. The number of partitions grows according to the Bell numbers, which increase very quickly. That is why the main challenge is usually not just writing the algorithm, but understanding that the output size becomes enormous even for moderate input sizes.

A Backtracking Strategy That Avoids Duplicates

The clean recursive idea is:

1. take the next element
2. place it into each existing block, one option at a time
3. also try starting a new block with that element

Because you only build partitions in one canonical construction order, you avoid generating duplicates that differ only by block ordering.

1def partitions(items):
2    result = []
3
4    def backtrack(index, blocks):
5        if index == len(items):
6            result.append([block[:] for block in blocks])
7            return
8
9        value = items[index]
10
11        for i in range(len(blocks)):
12            blocks[i].append(value)
13            backtrack(index + 1, blocks)
14            blocks[i].pop()
15
16        blocks.append([value])
17        backtrack(index + 1, blocks)
18        blocks.pop()
19
20    backtrack(0, [])
21    return result
22
23
24print(partitions([1, 2, 3]))

This function visits every valid partition exactly once. The blocks list represents the partition currently under construction.

Why the Copy Step Matters

Notice this line:

result.append([block[:] for block in blocks])

That deep-enough copy is essential. Without it, later backtracking steps would mutate the same lists that were already stored in result, and all saved partitions would eventually collapse into the same final state.

This is one of the most common errors in recursive combinatorics code.

A Generator Version Uses Less Memory

If you only need to iterate through partitions one by one, a generator is often better than collecting them all first.

1def generate_partitions(items):
2    def backtrack(index, blocks):
3        if index == len(items):
4            yield [block[:] for block in blocks]
5            return
6
7        value = items[index]
8
9        for i in range(len(blocks)):
10            blocks[i].append(value)
11            yield from backtrack(index + 1, blocks)
12            blocks[i].pop()
13
14        blocks.append([value])
15        yield from backtrack(index + 1, blocks)
16        blocks.pop()
17
18    yield from backtrack(0, [])
19
20
21for partition in generate_partitions([1, 2, 3]):
22    print(partition)

This version does not keep every partition in memory at once, which becomes important as the Bell number explodes.

Understand the Cost Before You Run It

There is no magic shortcut for "all partitions" because the output itself is huge. For example:

• 'n = 3 gives 5 partitions'
• 'n = 4 gives 15'
• 'n = 5 gives 52'
• 'n = 6 gives 203'

So the right optimization is often not micro-performance, but reducing the problem. If you only need partitions with exactly k blocks or blocks under a certain size, add that constraint to prune the search early.

Common Pitfalls

The biggest pitfall is generating duplicates by treating different block orders as different answers. A valid algorithm must use a consistent construction order so each partition appears once.

Another mistake is forgetting to copy the current partition before saving it. Backtracking mutates the working lists, so references cannot be stored directly.

The third issue is underestimating output size. Even a correct algorithm becomes impractical quickly because the number of partitions grows so fast.

Summary

• A set partition splits the elements into non-empty, disjoint blocks that cover the whole set.
• Recursive backtracking is the standard way to generate all partitions.
• The safe construction rule is to place each new element into existing blocks or a new block.
• Copy the current blocks before saving a result, or later mutations will corrupt earlier answers.
• The number of partitions grows according to the Bell numbers, so full generation becomes expensive quickly.