help to find An efficient algorithm

I'm trying to find An efficient algorithm for the following problem:

I have $n$ sets of numbers (different sets might have common numbers) and I need to find union combination of $k$ sets that Will yield the biggest set.

For example: if i have the sets $A1=\{1,3,4\}, A2=\{1,2,4\}, A3=\{5,7\}$ in that case $n=3$ and lets say that $k=2$.
$|A1 \cup A3| =5$ or $|A2 \cup A3| =5$ will yield the biggest set
In contrast to $|A1 \cup A2|$ = 4.

If this is np hard question (i don't know if it is) a good Approximation will be fine
I think that brute force is $O({n \choose k})$ operations.

Your problem is known as the Maximum coverage problem. If $S$ is a solution (a set of at most $k$ sets), then an element is covered if it belongs to $\cup_{X \in S} X$. You want to find a solution that maximizes the number of covered elements. This problem is known to be $\textrm{NP}$-hard (see below for a possible reduction) and admits a greedy approximation algorithm that will cover at least a $\left( 1- \frac{1}{e} \right)$-fraction of the elements covered by an optimal solution.

In addition, there is an easy reduction from $3$-SAT to your problem.

Consider an instance of $3$-SAT with $n$ variables $x_1, \dots, x_n$ and $m$ clauses $C_1, \dots, C_m$. You can obtain an instance of your problem by creating two sets $T_i$ and $F_i$ for each variable $x_i$. The sets are defined as follows:

• $T_i = \{ j \mid x_i \in C_j \} \cup A_i$ ;

• $F_i = \{ j \mid \overline{x_i} \in C_j \} \cup A_i$,

where $A_1, \dots, A_n$ are arbitrary pairwise-disjoint sets, each containing $m+1$ integers between $m+1$ and $m+n(m+1)$.

Deciding whether you can select $n$ sets such that their union has cardinality at least $m+n(m+1)$ is now equivalent to deciding whether the $3$-SAT formula is satisfiable.

StackExchange Computer Science Q#116809, answer score: 3