Rozkład liczby na sumę składników z określnego przedziału

Witam,
potrzebuję algorytmu, który wczyta dwie liczby: n i k, a następnie sprawdzi, czy liczbę n można rozłożyć na sumę k składników z przedziału 3-6 i jeśli można, to wypisze jedną z możliwości jej rozkładu.

Na przykład:
dla wejścia
9 2
wyjściem powinno być
3 6
lub
4 5

Luźny strzał: mógłbyś sprawdzić czy 3 <= n / k <= 6 i jeśli tak, to następnie zachłannie wypisać k trójek i dorzucać do każdej po kolei +1 tak długo, aż nie osiągniesz pożądanej sumy.

Albo iść od góry, sprawdzić o ile od, n jest większe, k * 6, i, odpowiednio pozamieniać szóstki na mniejsze liczby, (uwaga! Szczegóły implementacyjne) aby zbliżyć sie do, n ,kontynuować i albo dostaniemy, n, albo nie.

Dzięki za odpowiedź.
Niestety nie poznałem jeszcze programowania zachłannego, ale jakoś sobie poradziłem.

Hasło: backtracking, programowanie dynamiczne

https://www.geeksforgeeks.org/understanding-the-coin-change-problem-with-dynamic-programming/amp/

Zakładając, że liczby mogą się powtarzać (np. N=12, k=2 rozkłada się na 6 i 6) to bym zrobił tak:

1. Sprawdzasz, czy liczba N jest większa od 3k i mniejsza od 6k (czyli musi być w przedziale {3k;6k}).
2. Jeśli nie to nie da się takiej liczby rozłożyć na te czynniki.
3. Jeśli tak, to lecisz w pętli od najwyższej liczby, czyli od 6.
   4.1. Jeśli 6 jest mniejsze od twojej liczby i jednocześnie N-6 będzie się mieściło w przedziale {3*(k-1); 6*(k-1)} to zapamiętujesz szóstkę jako jeden z składników sumy, zmniejszasz k o jeden i liczbę N o 6.
   4.2. Jeśli warunki z 4.1. nie są spełnione to zmniejszasz 6 na 5 i powtarzasz kroki 4.1/4.2 od nowa.
4. I tak aż do momentu, w którym k będzie zerowe. Taka sytuacja musi wystąpić z prostej przyczyny - z 3 liczb z zakresu 3-6 da się ułożyć dowolną liczbę z zakresu {3k;6k}. Sprawa by była dużo bardziej skomplikowana, gdyby np. można było wziąć tylko liczby 4 i 6, ale tutaj to nie zachodzi.

Jeśli liczby się nie mogą powtarzać to sprawa się robi jeszcze bardziej trywialna.

1. Sprawdzasz, czy liczba k nie jest większe od 4. Jeśli jest - to się nie da.
2. Sprawdzasz, czy liczba N nie jest mniejsza od dolnego progu (czyli dla k=1 => 3, k=2 => 3+4, k=3 => 3+4+5, k=4 => 3+4+5+6), i większa od wyższego progu (k=1 => 6, k=2 => 6+5, k=3 => 6+5+4, k=4 => 6+5+4+3). Jeśli oba te warunki nie są spełnione - to się nie da jej złożyć.
3. Teraz lecisz od dołu lub góry, czyli bierzesz sobie np. i=6, sprawdzasz, czy twoja liczba N jest większa od i - jeśli tak, to zapisujesz sobie i jako składnik, a N zmniejszasz o i.
4. i zmniejszasz o 1.
5. tak aż twoje N nie zejdzie do zera.
   Znowu masz gwarancję, że N zejdzie do zera z powodu pkt. 2 w którym sprawdzasz progi.