Informatica Online Judge

  Subset Sum (Small) [0560 / 0230]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 216   Total Tried : 959


The Champion of this Problem (C++) : gs16117 - ms / 482byte
My Best Submission (C++) : N/A

[]

Background

정수 a1, a2, ... , an이 주어진다.

이 중에서 몇 개의 정수를 골라서 그 합이 k가 될 수 있는지 판정하시오.

단, 주어지는 정수 ai(1 <= i <= n)중 같은 값이 있을 수도 있으며 0이상 1,000,000이하의 값이다.

Input

첫 번째 줄에 n과 k가 공백으로 구분되어 입력된다.

[입력값의 정의역]
n <= 20 , k <= 1,000,000 (단, n, k는 자연수)

Output

n개의 정수 중 몇개를 골라 합을 구하였을 때 그 합이 k가 될 수 있다면 YES, 아니면 NO를 출력한다.

IO Example

입력
4 13
1 2 4 7

출력
YES

입력2
4 15
1 2 4 7

출력
NO

* 첫 번째 예의 설명

13 = 2 + 4 + 7 이므로 YES를 출력

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]