Rectangle 27 0

algorithm 5 numbers such that their sum equals 0?


ha[-1] = 1
ha[2]  = 4
ha[3]  = 1

After convolving all the histograms together with the FFT, the resulting histogram will contain entries where the value for each bin tells you the number of ways of combining the numbers to get each possible total. To find the answer to your question with a total of 0, all you need to do is read the value of the histogram for bin 0.

For example, the set a=[-1,2,2,2,2,3] would be represented by a histogram with values:

If the arrays contain integers of limited size (i.e. in range -u to u) then you can solve this in O(n+ulogu) time by using the fast Fourier transform to convolve the histograms of each collection together.

Note