Picking five numbers that sum to S

Given an array A of N nonnegative numbers, I'm interested in finding the number of ways you can pick 5 numbers (from distinct positions in the array) such that their sum is S.

There is an easy solution in O(N^3):

Let H be a hash table of (sum, position of leftmost element of sum)
for i = 0, N
    for j = i + 1, N
        H.add(A[i] + A[j], i)

numPossibilities = 0
for i = 0, N
    for j = i + 1, N
        for k = j + 1, N
            numPossibilities += H.get(S - (A[i] + A[j] + A[k]), k)

Where H.get(x, y) returns the number of elements in the hash whose sum has the same hash as x and whose leftmost element is bigger than k.

Alternatively, we can add sums of 3 elements to the hash table and then continue with 2 nested for loops. The complexity remains the same however, and we just use more memory.

Assuming the inputs will be fairly random (so no worst-case hashing), is there an algorithm that can solve this in O(N^2) or maybe O(N^2 log N), or even O(N^3) if it holds in all cases? I'm thinking binary searching might help, but I don't see how to deal with overlapping indexes.

The above solution is a lot better in practice than the naive 5-for-loops solution, however I have a feeling we can do a lot better, hence this question.

If you can prove that no such algorithm exists, how can the above solution be optimized?

Clarification:

The above algorithm is indeed O(N^5) in the worst case, such as when the given array contains nothing but the number 1 and we have S = 5. On average however, the H.get method is a lot closer to O(1), hence my average cubic complexity.

If you implement this and run it on 1000 random numbers in a big interval (say 0 upto Int32.MaxValue), you will see that it runs relatively fast. Still, it's not hard to find inputs for which it takes a long time. Even if we can't get it running fast enough for all equal numbers, what optimizations could we make?

Under the same assumptions, can we do better, asymptotically or at least in practice?