Различных комбинаций очень много. Так что, раз уж вы их все обходите, то полный перебор будет работать не сильно медленнее. Его потом можно соптимизировать.
Пишите рекурсивную функцию, которая получает на вход 2 параметра: сколько осталось добрать, какое максимальное слагаемое можно использовать. Текущие слагаемые или идут третьим параметром или вообще хранятся в глобальной переменной.
Функция перебирает 2 варианта. Пусть отсавшаяся сумма s, а разрешенное максимальное число имеет номер i (они хранятся в каком-нибуть отсортированном a[]).
1) Берем текущее максимальное слагаемое. Естественно, если оно помещается в остаток
s >= a[i]. Кладем его к текущим слагаемым в массив и рекурсивно вызываемся от уменьшенного остатка, не меняя максимальное число -
(s-a[i], i). Важно - если слагаемые хранятся в глобальной переменной, то надо после рекурсивного вызова "вернуть как было" - удалить только что добавленное слагаемое из массива.
2) Пропускаем текущее максимальное число. Значит, больше его брать вообще нельзя. Вызываемся от
(s, i-1). Естественно, этот вариант есть только если
i>0.
Если мы получили, что оставшаяся сумма
s равна нулю, то мы подобрали разбиение, надо вывести текущие слагаемые.
Ах да, чтобы этот метод хорошо работал имеет смысл слагаемые отсортировать по возрастанию. Чтобы сначала брались самые большие.
Если среди возможных слагаемых нет 1, то этот полный перебор может заходить в тупики. На пример, доступны слагаемые 6 и 11, надо набрать 29. Алгоритм может пропустить 11 и попытаться набрать 29 одними шестерками, но этого никогда не получится. Эти лишние тупиковые ветки можно обрезать и ускорить таким образом решение в некоторых случаях.
Для этого смотрите задачу
о рюкзаке. Почти как в ней сделаейте динамическое программирование, которое будет считать, сколько способов собрать заданную сумму k мешьшими слагаемыми. После этого в рекурсивной функции вы можете сразу же возвращаться, если ДП говорит, что вариантов набрать s первыми i слагаемыми - 0.
Кроме того, если вам нужно только количество вариантов, а не сами разбиения на слагаемые, то вам не нужен перебор, а нужно лишь динамическое программирование.
EDIT: Только заметил, что вам порядок важен и 1,2,3 считается отдельно от 3,1,2
Изменения просты - рекурсивная функция теперь принимает только один параметр - сколько осталость добрать. Вместо двух вариантов она перебирает N вариантов - какое именно число из разрешенных взять.
Оптимизация такая же. реализуете ДП, которое считает, сколько способов собрать заданное число и, если способов нет, возвращаемся из функции.
Средний
