Z kim się bawić

Mam okropny problem z jednym algorytmem. W ogóle nie potrafię wpaść na pomysł jak to ma działać( nie chodzi mi o stronę kodowania). Jedyne co się podowiadywałem o sposobach:

• Nie wiem czy to można nazwać sposobem, ale to jest podobno do rozwiązania wariacjami.
• Iteracyjnie( nie wiem w ogóle kto to rzucił mi to nie mówi nic, a dokładniej kojarzy się po prostu z pętlą, tablicą i i)
• Metodą "zachłanną" tutaj już miałem nawet ciekawy pomysł ładnie poszło na małych i prostych danych. Sprawdziłem dla innych. Nie chciałem nawet walczyć kilka lat z znajdywaniem coraz większej ilości błędów.

Nie proszę o czysty kod. Jeżeli ktoś chce to ok, ale bardziej preferuje aby ktoś mi wyjaśnił jakiś sposób na to zadanie. Poniżej daję zadanie( nie widzę żadnej opcji" spoiler" tak więc wrzucę czysto). Plus język w jakim to mamy napisać to cpp.

Dzieci wesoło wybiegły z Borsuka. Rodzice, z którymi przyleciały na Marsa już wiedzą z którymi rodzinami przyjdzie im dzielić osiedla. Dzieci jednak odkryły, że administracja Marsa nie poradziła sobie zbyt dobrze z tym podziałem. Mianowicie po wprowadzeniu się grup rodzin do przygotowanych osiedl w niektórych z nich młodych obywateli marsjańskich będzie tak dużo, że nieustanny hałas i harmider będzie naruszał domowy mir. W innych jednak dzieci będzie za mało i z nudów całe dnie będą grać w gry przy komputerach (wszystkie w ciągu roku dostaną skoliozy) lub zaczną szukać sobie innych rozrywek (niekoniecznie pochwalanych przez obowiązujące normy społeczne).

Rodzice na prośbę swych pociech wystosowali petycję do centrum dowodzenia, by przemyśleli kwestię podziałów. Inżynierowie z centrum stwierdzili, że najlepszym rozwiązaniem będzie połączenie ze sobą rodzin w taki sposób, by w każdej grupie rodzin była taka sama liczba dzieci i oczywiście by liczba grup rodzin była równa liczbie osiedli. Postanowili sprawdzić czy dla każdego miasteczka jest możliwe takie ułożenie.

Wejście:

Na wejściu program otrzymuje liczbę naturalną n, oznaczającą liczbę minimiast, dla których należy znaleźć możliwe rozmieszczenia. Następnie podanych jest n zestawów danych, z których każdy składa się z dwóch linii. W pierwszej z nich znajdują się dwie liczby naturalne r i o, gdzie r to liczba rodzin do rozmieszczenia w danym mieście, a o liczba osiedl. W drugiej jest r liczb naturalnych d1...dr, oznaczających liczbę dzieci w kolejnych rodzinach.

1<=n<=100
2<=r<=20
2<=o<=10
0<=di<=100

Wyjście:

Na wyjściu dla każdego miasta program ma wypisać liczbę wszystkich możliwych podziałów rodzin spełniających warunki lub wyraz "NIE", jeśli nie istnieje takie podział.

Przykład:

Wejście:
2
4 2
5 6 4 5
4 2
2 8 10 6
Wyjście:
1
NIE

Myślę, że należałoby wziąć brute force (tj. przeskanować wszystkie rozwiązania i zsumować te, które pasują) jako podstawę, a potem zastanowić się nad optymalizacjami. Nauczony doświadczeniem napisałbym właśnie brute force'a (chyba trywialne?), wrzucił do gita i przyrostowo implementował optymalizacje. A cóż możemy tu zoptymalizować...? Takie szybkie pomysły:

1. Policzyć ile dzieci jest w sumie, jeśli ta liczba nie dzieli się przez liczbę osiedli to nie ma sensu nawet próbować.
2. Gdy masz ilość dzieci w sumie, wiesz ile dzieci ma być w każdym osiedlu. Dzięki temu problem sprowadza się do zapełnienie n-1 kubełków m-elemetowych.
3. Dzięki temu interesują nas kombinacje, a nie wariacje "składów osiedli".
4. Jeśli posortujesz rodziny po liczbie dzieci, będziesz miał możliwość przewidzieć wcześniej, że nie ma sensu dalej szukać (gdy masz do dyspozycji tylko większe rodziny, a limit już przekroczyłeś).
5. Posortowane rodziny łatwo pogrupujesz po liczebności co również możesz wykorzystać.
6. Myślę, że warto się zastanowić kiedy warto zastosować dane optymalizacje (może się okazać, że dla małych zestawów nie warto)
   Powodzenia.

Ok, więc tłumacząc zadanie na normalny, formalny język:
Chcemy policzyć na ile możliwych sposobów możemy podzielić zbiór r-elementowy na o-podzbiorów, tak aby suma elementów w każdym podzbiorze była równa.