Yesterday we were trying to find the subsequence sums that are divisible by m. We noted that we were multiplying the sum of all elements with the sum of binomial coefficients. If one of the two components is divisible by m, then sum of all subsequences would also be divisible by m. In addition we could find the sub patterns to check the divisibility by m. For example we could enumerate subsequences that are individually divisible by m using the combine method with the condition for individual combinations to be added to the result only when their sum is divisible by m.
Another approach we demonstrated was to merely check for the presence of  a subsequence with a sum divisible by m. We translated this problem to 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(). Since we already know how to check if any subsequence has a sum equal to a given value using dynamic programming, this approach merely iterates over the possible candidates to target.

But we could go further into using the patterns of forming subsequences. We do this with the help of modulo because all sums will have to be in the modulo range 0 to m-1. We discuss this approach here.

This alternative way finds the sum of subsets that are divisible by m by 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]; 

        }