We were looking at an exercise involving sum of all numbers formed by subsequences in  the digits representing a number. This method was called Int GetSumOfAllSubsequences(List<int>A, int start, int end) 

We did this by choosing different numbers but we can also put to use the fact the number of such subsequences is represented by repetitions.  A digit will appear as many times as it is chosen in this combination. Therefore the sum is the accumulation of repetitions times the digit value. 

Let's take an example and see the pattern: 

a0, a1, a2 

can be combined as a0 + a1 + a2  + a0a1 + a1a2 + a0a2 + (a0a1a2 ) = 4(a0+a1+a2) where 4 = 1 + 2 + 1 

For a0,a1,a2,a3 we have 8(a0+a1+a2+a3) and 8 = 1 +3 + 3 + 1 

and these are infact the sum of the binomial coefficients. 

Int GetSumOfAllSubsequences(List<int>A, int start, int end) 

{ 

If (start>end) return 0; 

If (start==end)return A[start]; 

Int sum = A.Sum(); 

int sumofallsubsequences= 0 

For (int n = 1; n <=A.Count; n++) 

       Sumofallsubsequences += sum * GetNChoosekDP(A.Count-1, n-1) 

Return sumofallsubsequences; 

}

Said another way each element can either be taken or left from the subsequence. This happens in a total of Math.Pow(2, A,Count-1) ways. Therefore we could calculate the sum of all subsequences as :

A.Sum() x Math.Pow(2, A.Count-1)

Notice that this is in fact the summation of all the binomial coefficients, Specifically,

Coefficients              Total

         1                      Math.Pow(2,0)

       1   1                   Math.Pow(2,1)

     1   2  1                 Math.Pow(2,2)

and so on

If we were to find the subsequence sums that are divisible by m, we note 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.We could therefore find the sub patterns to find the divisibility by m. If we want to enumerate subsequences that are individually divisible by m, then we would use the combine method with the condition for individual combinations to be added to the result only when their sum is 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 PrintIsSubsequenceSumDivisibleBy(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]);

}