Mam podane n liczb naturalnych posortowanych niemalejąco i chciałbym wygenerować jakąś podaną liczbę pierwszych kombinacji tych liczb (nie więcej niż 1000) takich, że suma liczb w kolejnych kombinacjach jest coraz większa. Czyli np. dla liczb 2 3 6 8 i pięciu pierwszych kombinacji chciałbym dostać: 2 (suma 2), 3 (suma 3), 2 3 (suma 5), 6 (suma 6) i 8 (suma 8). Jeśli suma dwóch kombinacji będzie taka sama nie ma znaczenia którą wypisuje się najpierw. Ma ktoś pomysł na algorytm, który działał by w jakimś przyzwoitym czasie?
0
0
Robisz kolejkę priorytetową i wrzucasz do niej najmniejszą kombinację jednoelementową, najmniejszą dwuelementową, najmniejszą trzyelementową i tak dalej aż do najmniejszej n-elementowej. Następnie wyciągasz z kolejki tyle kombinacji ile potrzebujesz. Przy wyciąganiu k-elementowej kombinacji dodajesz do kolejki następną (w kolejności leksykograficznej) k-elementową kombinację (jeżeli taka istnieje).
Złożoność czasowa to na oko O(pnlog n) przy dobrej implementacji.