Please help me describe a dynamic programming algorithm to c

Please help me describe a dynamic programming algorithm to compute the number of feasible subsets that equal M, and please explain clearly the subproblems and the dependency relation of your dynamic programming algorithm.

These are the details of the problem.

We are given n items of sizes a₁,a₂,...,a_n, which are positive integers. We are also given a knapsack of size M, which is also a positive integer. We want to determine whether there is a subset S of the items such that the sum of the sizes of the items in S is exactly M. If there exists such a subset S, we call S a feasible subset.

In fact, it is possible that there are multiple feasible subsets. In this exercise, you are asked to design an O(nM) time dynamic programming algorithm to compute the number of feasible subsets.

For example, suppose the item sizes are 3,5,6,2,7, and M = 13. Then, there are two feasible subsets {6,7} and {2,5,6}. Thus your algorithm should return 2.

Solution

Let feasibleSubsets( S, M ), return the number of subsets in S, that sum out to be exactly M

Now, we can break this problem into two smaller subproblems. It has to be smaller, in order to always guarantee the termination of algorithm.

For each item i in S, we either choose that item , or do not for our subset

If we choose it, we get a new subproblem feasibleSubsets( S\' , M - i ) where S\' is S after i is removed from it, and i is value of the chosen item

If we don\'t choose it, we get a new subproblem feasibleSubsets( S\', M )   

Note that, even if we don\'t choose i, we still reduce problem with set as S\', because we have made decision for i, and don\'t want to repeat that again.

Now say, we somehow got solutions to   feasibleSubsets( S\', M-i ) and feasibleSubsets( S\', M ).

We add their values, to get subsets for S i.e.

feasibleSubsets( S, M ) = feasibleSubsets( S\' , M ) + feasibleSubsets( S\' , M- i )

Lets see time complexity of our algo,

Finally, we would have to find solutions for different values of S and M, right?

and all will be in O(1), once we got solutions of their subproblems ( just one addition is required)

So, that reduces time complexity to be O( |S|M ) = O(nM)