count of non-empty subsequences with integer average

Question

Is there any algorithm to count number of non_empty sub sequence of an array with integer average, expect the brute force way? Any dp solution?

for example for {2, 6, 2} we have 6 sub squences with integer average.

1. 2
2. 6
3. 2
4. 2 6
5. 6 2
6. 2 2

I tried brute force approach but I want better algorithm using DP.

Answer 1

Here is a straightforward O(n^4) algorithm.

def integer_average_subsequences (items):
    answer = 0
    for l in range(1, len(items)+1):
        counts = [[0] * l for _ in range(l+1)]
        counts[0][0] = 1
        for item in items:
            for j in range(l, 0, -1):
                for k in range(l):
                    counts[j][(k + item) % l] += counts[j-1][k]
        answer += counts[l][0]
    return answer

It may seem wasteful to redo the DP for each length. But if there are more than O(n^2) sums, it is actually faster to do it this way.