А без рекурсии никак не сделать, да?
Любой рекурсионный алгоритм можно переписать без рекурсии заведением доп-переменных, массивов и так далее. Это лишь вопрос соображения "понимать что происходит".
Рекурсия же очень удобна в т.ч. чтобы давать краткое описание того "что происходит".
И тут формулировка весьма простая. Попытаюсь еще раз её дать еще другими словами к тому что было сказано выше.
Вот пусть у нас массив из

элементов и заданная сумма

.
Рассматриваем какие значения может принимать 1-ая ячейка. Очевидно что от

до

, т.к. если будет больше, то даже одни лишь единицы в последующих ячейках превысят сумму.
Значит делаем цикл по значениям в первой ячейке от 1 до

, а дальше в каждой итерации этого цикла сводим задачу к такой же на

ячеек (остаток массива) и

минус текущее значение в этой самой первой ячейке. Т.е. запускаем алгоритм на остаток массива просто с текущими лимитами и всё.