Контест Senior Перебор с возвратом обновлено
Расставить плюсы и минусы: встреча посередине
Условие
Даны n положительных чисел a₁ … aₙ и число S. Перед каждым числом ставится знак + или −. Сколько расстановок дают в сумме ровно S?
Ввод: в первой строке n и S (1 ≤ n ≤ 30, |S| ≤ 3·10⁹), во второй n чисел (1 ≤ aᵢ ≤ 10⁸).
Вывод: число расстановок.
Пример 1
Ввод:
4 2
1 1 1 1
Вывод:
4
Пример 2
Ввод:
3 7
1 2 4
Вывод:
1
Как подойти
Подсказки: 2
- 2³⁰ вариантов слишком много, а 2¹⁵ уже немного.
- Переберите половины отдельно и сведите их хеш-таблицей.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Предыдущий вопрос
Сколько способов расставить n ферзей
Следующий вопрос
Все различные перестановки букв