Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
