A Coin Problem

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 128M

Problem type

Your parents have generously given you \(N\) types of coins with various denominations. They would like to know if there is some combination of coins that sum up to the value \(S\).

Input Specification

The first line will contain two integers \(N, S\ (1 \le N \le 100, 1 \le S \le 10\ 000)\).

The second line will contain \(N\) integers, \(c_1, c_2, \ldots, c_N\ (1 \le c_i \le 1\ 000)\) the denominations of the coins that your parents will give you. Note that the same denomination of coin may be used multiple times.

Output Specification

Print YES if it is possible to use some combination of the coins to sum up to \(S\), or NO otherwise.

Sample Input 1

3 6
1 4 5

Sample Output 1


Explanation for Sample 1

We can use \(6\) coins of value \(1\) to make the sum of \(S = 6\). Note that there are other ways as well.

Sample Input 2

2 11
3 7

Sample Output 2


Explanation for Sample 2

There are no ways to make \(S = 11\) with coins of value \(3\) and \(7\).

Sample Input 3

2 7
3 2

Sample Output 3


Explanation for Sample 3

We can use \(1\) coin of value \(3\) and \(2\) coins of value \(2\) to make a total sum of \(7\).