Киоск: сдача без сдачи

Ты зашёл в школьный киоск. У тебя в кармане лежат несколько купюр/монет с фиксированными номиналами. Продавец вредничает и просит заплатить ровно без сдачи. Каждую купюру можно использовать не больше одного раза.

Определи, получится ли набрать ровно нужную сумму.

Формат ввода

В первой строке записаны два целых числа n и S — количество купюр и нужная сумма. Во второй строке записаны n целых чисел a1, a2, ..., an — номиналы купюр.

Формат вывода

Выведи YES, если можно выбрать некоторые купюры так, чтобы их сумма была ровно S. Иначе выведи NO.

Ограничения

• 1 ≤ n ≤ 18
• 1 ≤ ai ≤ 1000
• 0 ≤ S ≤ 18000

Пример

Ввод:

5 11
1 2 5 9 10

Вывод:

YES

(например, 1 + 10 = 11)

Ключевое наблюдение: купюр всего до 18, значит количество всех вариантов выбора «взять/не взять» равно 2^n — это всего 262144. Такой перебор легко укладывается по времени.

Приём: битмаска (binary mask) — число от 0 до 2^n - 1, где i-й бит показывает, берём ли купюру a[i]. Почему работает: каждый набор купюр однозначно соответствует своей маске, и мы гарантированно проверяем все возможные подмножества.

План решения:

• Считать n, S и массив a.
• Для каждой mask в диапазоне 0 .. (1<<n)-1:
• Посчитать сумму выбранных купюр: пройти по i=0..n-1 и если бит включён — добавить a[i].
• Если сумма стала равна S, сразу вывести YES и закончить.
• Если все маски проверены и совпадения нет — вывести NO.

Мини-сниппет проверки бита:

• if (mask >> i) & 1: s += a[i]

Сложность: O(n * 2^n), при n=18 это около 4–5 миллионов операций.

Частая грабля: забыть, что сумма S может быть 0. Тогда подходит пустое множество (маска 0), и ответ должен быть YES.