Daca am inteles bine problema, atunci ar merge sa faci un fel de rucsac si pentru fiecare suma sa retii intr-un vector predecesorii.
ceva de genu
for (int i = 1; i <= nrc; ++ i)
for (int j = S; j >= 0; -- j)
if (s[j] && j + cost[i] <= S) {
s[j + cost[i]] = 1;
pred[j + cost[i]][ ++ lung[j + cost[i]]] = j;
}
si dupa setezi cate o suma <= S si iei toti predecesorii la rand.
Solutia asta nu merge decat in cazul in care numarul de cabane si S-ul sunt acceptabile ( ca valori)
. Oricum pentru valori mari cred ca exista prea multe drumuri pentru a fi afisate toate.
Oricum enuntul mi se pare destul de "vag"
... Ar putea merge si cu Backtracking