eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Суммирование

Суммирование

Лимит времени 0.1 секунд
Лимит использования памяти 64 MiB

Для заданной суммы и списка возможных слагаемых, являющихся целыми числами, найти все способы получения заданной суммы. Например, если заданна сумма 4 и список чисел 4 3 2 2 1 1, то получим

Sums of 4: 4 3+1 2+2 2+1+1

Входные данные

Входной файл может содержать произвольное количество тестов. Данные для каждого теста могут занимать одну строку. Первые два числа указывают сумму и количество чисел в списке. Далее содержится сам список чисел. Все числа будут разделены одним или несколькими пробелами. Числа в каждом списке отображаются в порядке убывания, но могут быть повторения. Всего будет не более 12 чисел в каждом списке, и каждое число будет положительным целым числом меньшим 1000. Сумма является положительным целым числом меньшим 1000.

Выходные данные

Для каждого набора входных данных выведите сначала строку с сообщением "Sums of", и дальнейшим значением самой суммы. Далее перечислите суммы по одной в строке. Если нет возможности набрать такую сумму, выведите строку "NONE". Числа в каждой сумме должны быть в порядке убывания. Число может быть повторено в сумме столько раз, сколько оно было повторено в первоначальном списке. Каждый тест для суммы должен быть отсортирован так, как это показано в примере выходных данных. При выводе списка сумм не должно быть никаких дублирующих строк. Каждая строка должна быть выведена с новой строки. Выводите одиночные пробелы до и после слова " of ".

Пример

Входные данные #1
4 6 4 3 2 2 1 1
5 3 2 1 1
Выходные данные #1
Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE