## Editorial for A Coin Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ninjaclasher

This is a very classical dynamic programming problem.

Let $$dp[x]$$ denote whether it is possible to make a sum of $$x$$ using the given coins.

$$dp[x]$$ would be true if any of $$dp[x-c_i]$$ is true.

Thus, after computing the DP table, we can check $$dp[S]$$ to determine whether we can make a sum of $$S$$ or not.

Time Complexity: $$\mathcal{O}(SN)$$