dynamic pseudo-code for simplified coin changing algorithm
Given an integer $M&gt;0$ and $n$ coins with integer values $v_1, v_2,\cdots, v_n$, where $M, n, v_i$ are positive, how can we determine if some of the coins can add up to $M$?

This problem is a common version of subset sum problem. There are many strategies to solve the problem.



Here is the pseudocode by dynamic programming that is about as simple as possible.


Let $s$ be an array of size $M+1$ with default value 0 and starting index 0. Let $s[0]=1$.
For $i$ from 1 to $n$, do:


For $j$ from 0 to $M$, do: 


If $s[j]=1$, let $s[j+v_i]= 1$.


If $s[M]=1$, return yes. Otherwise, return no.


Here is an example to illustrate the algorithm. Let $M=7$. Coins are $1,3,3,5$.


$s=[1,0,0,0,0,0,0,0]$.
Here are $s$ at the end of each iteration.


$s=[1,1,0,0,0,0,0,0]$
$s=[1,1,0,1,1,0,0,0]$
$s=[1,1,0,1,1,0,1,1]$
$s=[1,1,0,1,1,5,1,1]$

return yes since $s[7]=1$


We can optimize the algorithm above in various ways. 


We can stop the algorithm once we have found $s[M]=1$. 
We can change $s$ to a double linked-list, whose elements are the realizable values in increasing order.
We can split the given array of values to two arrays of equal size or sizes with difference 1. Run the algorithm on each of two arrays. Check if we can select one number from each resulting array $s$ such that their sum is $M$, using two-pointer technique. 
This last item means all other ways, as always.  




Exercise. Adapt the algorithm so that it also tells the least number of coins used if the answer is yes.