Mam następujący problem:
Napisać algorytm obliczający, na ile sposobów można wyrazić liczbę naturalną N w postaci sumy składników naturalnych.
Przykład:
N = 5
Zbiór sum = {5, 4 + 1, 3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1}Uwaga!
Sumy różniące się tylko porządkiem składników liczymy tylko raz (np.: 4 + 1 oraz 1 + 4).
Nie bardzo wiem, jak się do tego zabrać. Próbowałem na wiele sposobów, jednak zadanie mnie przerasta. Teoretycznie wydaje mi się, że problem jest raczej dość standardowy, ale nie byłem w stanie nic wygooglować.
Oczywiście nie chodzi mi o to, że ktoś wklei mi tutaj kompletny kod - takie coś mnie nie interesuje. Chciałbym jedynie, abyście mnie naprowadzili, zarysowali algorytm, podali jakiś pseudokod funkcji rekurencyjnej (gdyż zakładam, że tak trzeba to zrobić). Jednym słowem, chciałbym wiedzieć od czego mam zacząć i od której strony mam to zadanie ugryźć.