For a set of the form `A = {1, 2, 3, ..., n}`

. It is called partition of the set `A`

, a set of `k<=n`

elements which respect the following theorems:

a) the union of all the partitions of `A`

is `A`

b) the intersection of 2 partitions of `A`

is the empty set (they can't share the same elements).

For example. `A = {1, 2,... n}`

We have the partitions: `{1, 2, 3}`

`{1, 2} {3}`

`{1, 3} {2}`

`{2, 3} {1}`

`{1} {2} {3}`

These theoretical concepts are presented in my algorithms textbook (by the way, this subchapter is part of the "Backtracking" chapter). I am supposed to find an algorithm to generate all the partitions of a given set. I was struggling with this problem all the day and I couldn't find a solution. Can you explain me how does this algorithm work? Also, can you give me a pseudo-code sketch of the algorithm?

# Best How To :

You can try the recursive answer if your set is not to big (or else use stack) :

The principle is the following, you have a function that give back :

```
rec_func(SET) = List of List of Set
```

And work as follow :

```
rec_func(SET) =
if SET = {empty}:
// if no element, easy to give the answer
return([[]])
else:
// 1. Remove one element from the set : 'a' to this set
a = SET.pop()
// 2. Call rec_func :
list_of_list_of_set = rec_func(SET\'a')
response = []
// 3. For every possibilities given by the function add the element 'a' :
For every list_of_set in list_of_list_of_set :
// Case 1, you add 'a' to list_of_set
response.push( [{'a'} + list_of_set] )
// Case 2, for every set, you create a copy where you add 'a'
for every set in list_of_set:
response.push( [{set,'a'} + list_of_set\set] )
// The function return the list of list of set created.
return(response)
```