[stackoverflow] [algorithm] Smashing sets together

Marxist feminist game developer Anita Leigh Goldbergstein is given N sets, e. g.:

★ <a, b>
★ <a, d>
★ <c>
★ <d, e>
★ <b, f, c>

She wants to merge them in such way that:

1⟩ resulting list of sets is the smallest possible,
2⟩ operations on sets that have non-null intersection (that is, if an element appears in both) are strictly forbidden.

For the data above, the smallest list will be:

★ <a, b, c, d, e> -- from 1, 3, 4
★ <a, b, c, d, f> -- from 2, 5

What algorithm would you donate to her to solve this problem‽

Actually no. There are 4 * 4 possible ways to transition from the OP's state to a smaller state. 4 * 4 / 2 actually because set union is commutative. From each of these, there are ceil(3 * 3 / 2). Etc. Therefore complexity of a bruteforce solution is n^4 (n^2 because obviously, another ^2 because each transition can involve any pair of sets)