Даны цифры и целевая сумма S. Выведите все числа (любой длины), составленные из данных цифр, сумма цифр которых равна S. Цифры могут повторяться.
Формат входных данных
Первая строка: цифры через пробел (от 1 до 5 цифр, все цифры > 0)
Вторая строка: целевая сумма S (1 ≤ S ≤ 15)
Формат выходных данных
Все возможные числа с суммой цифр = S, каждое на отдельной строке. Числа выводить в лексикографическом порядке. Если решений нет, вывести "NO"
ПОДСКАЗКА:
Используй отсечение! Если текущая сумма уже больше S, дальше искать не нужно — это экономит время.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 2
4
|
1111
112
121
211
22
|