# Minimum number of subsets to combine to get a main set of numbers

We are given n sets of numbers, {1,4}, {4,5}, {1,2,3}. We have to find the minimum number of sets to combine to get the complete set of numbers {1,2,3,4,5}. Also, we should know which sets we selected.
Example:
If we choose {1,2,3} & {4,5}, we get the complete set in the minimum most number of steps = 2.
If we choose {1,2,3}, {1,4}, {4,5}, we get the complete set of numbers, but we would require 3 steps.
How do I solve this problem?

Sounds like a NP hard problem. Do you have any use case where this is required? Probably there are extra constraints?

The constraints can be as follows:
The number of subsets can be 35. Each subsets will have a max of 48 elements.
So, we can expect that the main set can have a max of 1680 unique elements.
Time constraint is not an issue.

if u have 35 subsets, you need to check 2^35 combinations max, it should run in an hour I guess if time is not a constraint.

For more optimization, Say you have 35 subsets and N=1680 max elements. you could break it down into 2 set of subsets, take the first 18 subsets in set A and rest in set B, so that gives N=2^18 choices for choosing something from A. (which is huge but not that much, 262044). for each of these N choices, you can store the list of missing elements from N (for example using a bitset of length N). You put these bitsets in a hash table, (in case of a collision, you know you need to take the one corresponding to the smaller subset from A). So you have a hash table of max K= 2^18 keys. (this can be pruned a bit if you look at union of B and also handle collisions).
Now for each of the 2^17 subsets of B, you search if itâ€™s corresponding bitset is in the hash table.
Theoretically, this should run in at most a minute.