Find sum of subsequences of a given sequence of positive integers that are divisible by m

We could translate this problem as find if there is any subset in the sequence that has sum 1x m, 2 x m, 3 x m, ... n x m where n x m <= sequence.sum()

void PrintSubsequenceSumDivisibleBy(List<int>seq, int m)

{

   for (int sum = m; sum <= seq.sum(); sum=sum+m)

         if (IsSubSeqSum(seq, seq.Count, sum))

             Console.WriteLine(sum);

}

bool IsSubSeqSum(List<int> seq, int n, int sum)

{

if (sum == 0) return true;

if (sum < 0) return false;

if (n == 0 && sum != 0) return false;

if (seq[n-1] > sum)

     return IsSubSeqSum(seq, n-1, sum);

return IsSubSeqSum(seq, n-1, sum) || IsSubSeqSum(seq, n-1, sum-seq[n-1]);

}

 

There is an alternative way to find the sum of subsets that are divisible by m. It involves recognizing that subsets will have sum whose modulo varies over 0 to m-1. Each element of the input either counts by itself or as  part of a subset. If we populate a boolean DP table for this range of 0 to m-1 and iterate over the elements then each element sets its corresponding cell in the DP table by itself. When it is a part of a sequence, we can repeat the problem considering any of the previous modulos and setting the corresponding cell in the DP table. This subproblem only happens for each of the modulo in the range only once. Therefore the inner loop is linear and we initialize a new sum array prior to iterating. Each cell of this new sum array for 0 to m-1 can be true or false indicating that the DP table for that corresponding index will be set to true because we have now formed a subset.  When we select the candidate modulo in the inner loop per the iteration, the new sum is the displaced modulo by the inclusion of the current element, The selection only happens when the dp entry for the candidate modulo is true and the new sum entry is false indicating we are forming a subset with a prior modulo and a new subset. As subsets keep forming and as the new sums get set with true, each corresponding DP table entry gets set. Eventually we return the value of the cell corresponding to m=0. In fact, we can bail early if we encounter it any sooner.

static bool HasSubSetSumModuloMEqualsZero(List<int> arr, int n, int m)

        {

            if (n > m)

                return true;

             var DP = new bool[m];

 

             for (int i = 0; i < n; i++)

             {

                 if (DP[0])

                     return true;

                 var temp = new bool[m];

                 for (int j = 0; j < m; j++)

                 {

                     if (DP[j] == true)

                     {

                         if (DP[(j + arr[i]) % m] == false)

                             temp[(j + arr[i]) % m] = true;

                     }

                 }

                 for (int j = 0; j < m; j++)

                     if (temp[j])

                         DP[j] = true;

                 DP[arr[i] % m] = true;

             }

            return DP[0];

        }