Find all subsets whose sum modulo a value is 0.

Question

How can we find the count of number of subsets of a given set (e.g. {1,7,4,90,23} ) whose sum is a multiple of a given value A.

One method which I know of is to store all subset sums modulo A and then for each new value find the subset sum with all existing subset sums modulo A. But can this be done more efficiently.

Answer 1

You want to work in $\Bbb{Z}/A \Bbb{Z}$ ie the integers modulo $A$, also sometimes written $\Bbb{Z}_A$. The reason is because if you find all subsets of $\Bbb{Z}_A$ that sum to $0$, then you can automatically find all integer subsets as well since if $\{a,b,c\}$ is a solution, then $\{a', b', c'\}$ is a solution for all $a' = a + Ak_1$, $b' = b + Ak_2$, and so on, where $k_i$ are some integers. This is the definition of modular arithmetic. Conversely if $\{a', b', c'\}$ is some integer solution, then there exist some solution $\{a,b,c\}$ in $\Bbb{Z}_A$ that corresponds to it.

Here's an algorithm that works on $\Bbb{Z}_A$, which has the underlying set $\{0, 1, 2, \dots, A-1\}$, ie, it has $A$ elements.

The only singleton (1-element) sets that sum to $0 \pmod A$ is $\{0\}$ itself. Next let's work on the 2-element sets. The only way to sum to $0$ with $\{a, b\}$ is to let $b = -a$ as $\Bbb{Z}_A$ is indeed an additive group. Thus there are $\{1, A-1\}, \{2, A-2\}, \dots$ so a total of $A/2$ 2-set solutions if $A$ is even and $A/2 - 1$ if $A$ is odd. Remember to each of the above 2-sets you can add a $0$ to the set and you have another solution.

Now take the 2-sets $\{a, b\}$ and solve $x + y = a$ to form the 3-sets $\{x, y, b\}$, and then solve $x + y = b$ to form the 3-sets $\{x, y, a\}$. Maybe if you do it in a certain way you can avoid repeats.

Also, your question wasn't clear, can you use multisets $\{a, a, b\}$ or only regular sets $\{a,b\}$??