The most efficient algorithm for computing cardinality of sumset Let A and B be two finite non-empty sets of positive integers. Their sumset is the set of all possible sums a + b where a is from A and b is from B. For example, if A = {1, 2} and B = {2, 3, 6} then A + B = {1 + 2, 1 + 3, 1 + 6, 2 + 2, 2 + 3, 2 + 6} = {3, 4, 5, 7, 8}.

As we can see, cardinality #(A + B) is less than sum of cardinalities #A + #B. So i wonder whether we can calculate #(A+B) faster than just calculating all #A + #B sums and inserting them in some set-like data structure.

I've tried searching "sumset cardinality algorithm" and so on but didn't succeed.

P.S. We may assume that there is some constan K, not very lare - for example 10^5, such that 1 &lt;= #A, #B &lt;= K and all the elements of A and B are between 1 and K
Use the FFT.  The characteristic vector of $A+B$ is the convolution of the characteristic vectors for $A$ and for $B$.  Convolutions can be computed efficiently using a FFT.  As long as every element of $A,B$ is not too large, this will be efficient: the running time will be approximately $O(n \lg n)$ if $A,B \subseteq \{1,2,\dots,n\}$.