Ето моето решение:

http://www.heypasteit.com/clip/28LG

На C++ е но не би трябвало да представлява проблем, а и кода е малко.

Не съм сигурен къде точно ти е проблема, но пробвах с моето решение случая, който описа и сработи.

Най-лесният вариант, според мен, който съм го направил е да тръгнеш от най-голямата монета.
Да кажем, че имаш 13 с монети от 5, 2, 1. Тръгваш с петиците и я слагаш, следващат рекурсия я почваш със сумата -5 и пак с петици, когато стигнеш до следващата по стойност монета, всяка следваща рекурсия я почваш с нея, а не се връщаш на петиците.

private static void GetCombination(int target, int[] nums, List<int> temp, int startIndex)
{
    if (target == 0)
    {
        AddCombination(temp);
    }
    else if (target > 0)
    {
        for (var i = startIndex; i >= 0; i--)
        {
            int num = nums[i];
            target = target - num;
            if (target >= 0)
            {
                temp.Add(num);
                GetCombination(target, nums, temp, i);
                temp.RemoveAt(temp.Count - 1);
            }
            target = target + num;
        }
    }
}

В startIndex пазя до коя монета съм стигнал последно.
Според мен ключовото е започването от startIndex, като следващата рекурсия започваш или от него или от следваща монета, но никога назад.

Прегледах кода, но не ми е ясно как работи при неограничено количество от всяка монета. Доколкото разбирам, имаш краен брой монети, минаваш през всички, тестваш всички възможни суми и вземаш комбинациите, които покриват условието.

Моето решение работи с неограничени монети, защото когато искам да генерирам следващата монета, не започвам от индекса на следващата монета, а от индекса на текущата.

FindSumElements(currentIndex + 1, index, sum - numbers[index]);

Това е (index) а не (index - 1)

Ето го моето решение на тази задача: 

http://pastebin.com/8fMVvcct

http://pastebin.com/rvDF3u7G Това е моето решение на тази задача, което също е рекурсивно. Моят въпрос обаче е, не трябва ли да измислим по-бързо решение от рекурсивното, за този тип проблеми.. аз си блъсках главата доста време и с 3та, и 4та, а пета въобще не успях да я реша.. Убеден съм, че ако реша подобна задача рекурсивно на изпита, ще ми изгърми за време в 80% от тестовете.. но някак така и не успявам да измисля решение с DP.. Според мен ще е хубаво да качват някъде и авторските решения на задачите от домашното, за да можем да свикнем с този тип мислене... междувременно ако някой може да ми хвърли решение на 5тa и на 3та задача, като 3та да не включва сортиране на числата, защото е много бавно.. Благодаря.

Аз я реших итеративно:  http://pastebin.com/GVXtfats

Със сигурност е възможно и още по-оптимално, но мисля, че това е достатъчно просто и оставих рекурсивния вариант да го направя по-нататък като упражнение. Просто се използва рекурентната връзка:

memo[row, col] = memo[row - 1, col] + memo[row, col - coins[row]]

 при пълненето на матрицата и търсеният резултат излиза най-долу вдясно - както при повечето задачи от този тип.

Моето решение на 4-та задача, което дадох, не използва рекурсия и е използвано DP.

@iliqnvidenov

Според мен проблема не идва от използването на рекурсия, а от това че използваш рекурентна връзка, при която е трудно да се приложи DP. Виж в добре познатата книга "Програмиране = ++Алгоритми" - там ги има решени тези задачи с рекурсия. Примерите са на C, но това предполагам няма да ти е проблем. Според мен обаче там обясненията са доста зле, въпреки че колекцията от алгоритми наистина е много добра. Едно пояснение или псевдокод от wikipedia често са ми по-полезни от написаното в тази книга. Но хората са различни - за теб написаното там може да се окаже много по-полезно.

Ако си добре с Индийския това също може да ти е полезно за рекурсивния вариант: https://www.youtube.com/watch?v=Kf_M7RdHr1M&list=PLtE7QNA19r-ZKVXrXBjqe-pkpjsnklxjh&index=10

Всъщност успях да измисля някакъв вариант на тази задача с ползване на DP.. проблема явно е, че за пръв път виждам подобен вид начин на мислене и ми се струва малко като магия.. блалала.. но съм убеден, че с малко повече труд ще станат нещата.. БЛАГОДАРЯ за линковете. Просто в това домашно се старах да не използвам рекурсия, а само DP, което явно не ми е все още по силите. :D