Дан набор различных положительных чисел и целевая сумма S. Найдите все подмножества, сумма элементов которых равна S. Каждое число можно использовать не более одного раза.
Формат входных данных
Первая строка: числа через пробел (от 2 до 8 чисел)
Вторая строка: целевая сумма S
Формат выходных данных
Все подмножества с суммой S, каждое на отдельной строке. Числа в подмножестве выводить через пробел в порядке возрастания. Подмножества выводить в лексикографическом порядке. Если решений нет, вывести "NO"
Примечание
В тестовом примере возможны только две комбинации
2+3+5=10
3+7=10
Другие комбинации не дают сумму 10.
ПОДСКАЗКА:
Для каждого числа есть два варианта: взять его или не взять. Используй отсечение: если текущая сумма уже больше S, дальше искать не нужно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 5 7
10
|
2 3 5
3 7
|