Вес для коробки

На заводе робот собирает коробку на отгрузку. На конвейере лежат детали с разными массами. Робот может взять любую часть деталей (каждую — не больше одного раза), чтобы суммарная масса получилась ровно такой, как требует наклейка.

Определи, сможет ли робот собрать коробку нужной массы.

Формат ввода

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

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

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

Ограничения

• 1 ≤ n ≤ 30
• 0 ≤ T ≤ 1000
• 1 ≤ ai ≤ 1000

Пример

Ввод:

5 11
2 9 4 6 3

Вывод:

YES

(Например, можно взять детали масс 2 и 9.)

Ключевое наблюдение: нас интересует только «можно ли набрать сумму s», где 0 <= s <= T. Большие суммы можно не хранить — всё равно они не помогут получить ровно T.

Подходит динамическое программирование по сумме: пусть dp[s] = True, если некоторым набором уже просмотренных деталей можно получить сумму s. Для новой детали массы x мы либо не берём её, либо берём и переходим из s в s + x. Чтобы не взять деталь дважды, обновление делаем «с конца» (или используем битсет).

Быстро и удобно делать битсетом: число dp, у которого бит s равен 1, если сумма s достижима. Тогда добавление детали — это сдвиг и OR:

dp = dp | (dp << x)

и после этого можно обрезать биты выше T, чтобы не разрасталось.

План:

• Прочитать n, T и массив масс.
• Инициализировать достижимые суммы: сначала достижима только 0.
• Для каждой массы x обновить достижимость (через битсет-сдвиг или булевый массив).
• В конце проверить, достижима ли сумма T, и вывести YES/NO.

Сложность: O(n * T) операций в варианте с массивом; с битсетом обычно ещё быстрее на практике (работа с целыми числами).

Частая ошибка: обновлять dp по возрастанию s в булевом массиве — тогда одна и та же деталь может «использоваться» несколько раз в рамках одного шага. Нужно идти по s от T к x или использовать битсет.