# Determine if there is a subset of the given set with sum divisible by a given integer

I've been given a question to solve:

Given a set of non-negative distinct integers, and a value $$m$$, determine if there is a subset of the given set with sum divisible by $$m$$.

For this question the answer is here

I don't understand the part after if DP[j]==True
what is actually the intuition behind this code. Please explain in detail.

• What do you make of the description at geeksforgeeks.org? – greybeard Sep 6 '20 at 6:13

Let f (i, k) = true if and only of there is a subset of the first k integers with a sum equal to i modulo m. As an example, if a[12] = 75, then f (i, 12) is true if and only if either f (i, 11) is true or f ((i-75) modulo m, 11) is true. And obviously f (i, 0) is true if and only if i = 0.

So if you have n integers, create a two dimensional array of size m * (n + 1), then fill array [i, 0] for all i, then fill array a [i, 1] for all i, and so on until you filled a [i, n] for all i. And there you have the solution.

Next you figure out how to do this without using an array of (n+1) * m elements, and you figure out when you can stop early because you know the answer already.

And I would be curious if there is any reason why these numbers would have to be a set.