$3.(7$ points$)$ Given a value N$,$ if we want to make change for N cents, and we have infinite supply of each of S $=\{$S$1,$ S$2,..,$ Sm$\}$ valued coins, how many ways can we make the change? The order of coins doesn$$t matter, so different permutations of the same coin sets are ignored. Prove the necessary traits of the problem to determine an algorithm

For example, for N $=4$ and S $=\{1,2,3\},$ there are four solutions: $\{1,1,1,1\},\{1,1,2\},\{2,2\},\{1,3\}.$ So output should be $4.$ For N $=10$ and S $=\{2,5,3,6\},$ there are five solutions: $\{2,2,2,2,2\},\{2,2,3,3\},\{2,2,6\},\{2,3,5\}$ and $\{5,5\}.$ So the output should be $5.$