Yesterday's post we discussed continuous subsequence.
Let us now generalize the above to finding subsequence ( that are not necessarily continuous and those that can repeat and should be counted as many times when there are duplicate subsequences at different positions) and again we want the subsequences whose sum is divisible by a number N.
In this case too we find prefixes. Note that the prefixes for subsequences are formed by taking the prefixes upto but not including the last element of the current prefix and then adding the set of prefixes formed by including this last element in each of the previous set of prefixes. for example, a set 3, 2 has empty set, 3, 2 and 3,2 as the prefixes when prefix length is two. We find and count this number of prefixes for all the prefix length 0 to N-1.
We use the principle that the number of sequences of the prefix , for which the sum of elements modulo 5 equals K, = sum of the same target for prefix shorter by one position
and the number of subsequences of a prefix shorter by one position for which the sum of elements modulo 5 equals K-x where is the last element of the given prefix.
We now calculate the number of subsequences for all the prefixes as a table where we take different prefix lengths as columns ranging for 0 to N-1 and remainders 0 to N-1 as rows
for example the first cell would correspond to 1 because an empty set satisfies the condition
the second cell with prefix length 1 would include this empty set plus the number of subsequences whose sum modulo 5 equals 5 - 3= 2 which in this case is 0 and consequently, the second cell is also 1. the last cell will have the answer to the question.

Now let us apply that to coin counting.  If we are given a set of coins with the following denomination:
                  1,1,2,5,7,17,17,35,83
we have to find the smallest positive integer for the amount of money that cannot be paid by the given coins.
Intuitively, the sum of the coins plus one would be that amount but how do we prove that this is so with the principle we just discussed.
Using just two coins we can pay any amounts upto 2. Using the next coin together with these two  extends the amount to 4. Using the next coin, we can pay any amount 0 to 4 with the first set of coins and not use the coin 5 and if we use the coin 5 we can pay from 0 to 9. if x is the amount  between 5 to 9, we use coin 5 and the coins from 5 -x to pay. This we can generalize as follows:
If the range of amounts that can be paid using the first k coins is from 0 to r, and the next coin has  value x, then either :
x <= r + 1 and it is possible to pay any amount from 0 to r+x using the first k+1 coins
x > r + 1 and it is not possible to pay r + 1 since x and all the next coins are greater values.
Using this principle we can now generate the table of values with each incremental denomination as follows:
           denomination    1   1   2   5   7    17   17    35    83
           max amount      1   2   4   9   16  33   50    85    168
And therefore the maximum amount that we cannot pay with the coins is 168 + 1 = 169.

Courtesy: Kubica and Radoszewski

Next we will review increasing subsequence.
But first a coding question:
 

Print Fibonacci int Fibonacci(int n)  { if (n == 0 ) return 0; int value = F(abs(n)-1) + F(abs(n)-2); if (n < 0) return power(-1, n+1) * (value);  return value; }