Задачи о подмножестве с заданной суммой
Дано множество из n целых чисел, а также q запросов. В каждом запросе указывается целое число . Для каждого запроса требуется определить, существует ли такое подмножество исходного набора чисел, сумма элементов которого равна .
Входные данные
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ 500).Во второй строке записаны
n целых чисел через пробел: (1 ≤ ≤ 100000), которые образуют исходное множество.Третья строка содержит одно целое число
q (1 ≤ q ≤ 100000), обозначающее количество запросов. Каждая из последующих q строк содержит одно целое число (1 ≤ ≤ 100000), которое является целевой суммой для i-го запроса.Выходные данные
Выведите
q строк, в каждой из которых укажите Yes или No в зависимости от того, существует ли подмножество чисел, сумма которого равна соответствующему запросу.Пример
Входные данные | Вывод |
4
1 2 5 7
5
4
3
10
14
11 | No
Yes
Yes
Yes
No |
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 1 MB