Given array A[] and B[], to find how frequently each possible sums A[i] + B[j] appears we can use FFT
For example A = [1,2,3], B = [2,4].
The sum 3 can be obtained in 1 way, sum 4 : 1 way, sum 5 : 2 ways, sum 6 : 1 way, sum 7 : 1 way
The way we can do this is to construct two polynomials, P and Q with their power corresponding to the element of the array. And apply the regular FFT.
So is there an efficient way of backtracking the numbers that forms the above. To elaborate, we know 3 can be formed in 1 way. But how do we know which two numbers form it?
One way to do it would be the classic two sum algorithm, i.e given an array and a target sum. Find the pairs that create the sum. Which is O(n) Given we can have N different targets, the resulting algorithm is O(n^2). But I want to keep it under O(nlogn).