Суммирование
Суммирование
Для заданной суммы и списка возможных слагаемых, являющихся целыми числами, найти все способы получения заданной суммы. Например, если заданна сумма 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 ".
Пример
4 6 4 3 2 2 1 1 5 3 2 1 1
Sums of 4: 4 3+1 2+2 2+1+1 Sums of 5: NONE