Podzbiory o sumie, która nie przekracza zadanej wartości

Problem wydaje mi się na tyle nietrywialny, że wolę zapytać na forum.

Dany jest zbiór, np. z = [3, 5, 6, 9].
Dana jest wartość, np. w = 10.

Trzeba wygenerować podzbiory zbioru z, których suma nie przekracza wartości w.
Dla powyższego przykładu podzbiory będą takie:

[3, 5]
[3, 6]
[9]

Samotnych 3, 5, 6 nie potrzeba, bo są uwzględnione w różnych podzbiorach.
Filtrowanie dużej ilości permutacji pod tym kątem może znacząco przekroczyć limity czasu.

Czy ten problem ma jakąś nazwę? Linki anyone ;) ?

To najbliższe co znalazłem: https://www.geeksforgeeks.org/count-of-subsequences-in-an-array-with-sum-less-than-or-equal-to-x/
Liczy sumy zamiast zwracać podciągi, do tego zwraca więcej wyników niż chcesz - ale wydaje się że akurat na koniec można to przefiltrować.

Dokładnie tak jak jest w linku powyżej, tego typu problem rozwiązuje się dynamicznie, nie ma lepszego sposobu. Aczkolwiek zwykle wystarczy zliczyć ile takich podzbiorów jest, bez wypisywania poszczególnych podzbiorów, no ale to pikuś jak już się wie jak ugryźć zadanie.

@neves: Niestety to zadanie nie kończy się na wygenerowaniu tych podzbiorów, bo potem trzeba policzyć ile elementów ma najdłuższy ciągły podzbiór w zbiorze z numerkami odpowiadającymi indeksom wartości zbioru z :(

Najdłuższy ciągły podzbiór spełniający ten warunek jest znacznie łatwiej i szybciej wyznaczyć niż wszystkie podzbiory spełniające ten warunek.

Prosty zachłanny algorytm się nada. Iterujemy od lewej do prawej po elementach zbioru. Będziemy potrzebowali dwa wskaźniki L i P oznaczające początek i koniec naszego ciągłego podzbioru.
W każdej iteracji dodajemy jeden element z prawej strony (P = P + 1) i zdejmujemy tyle elementów (x) z lewej strony (L = L + x) by podzbiór spełniał warunek. No i maksa liczymy ze wszystkich w ten sposób wyznaczonych ciągłych podzbiorów.

O, nawet ten algorytm ma nazwę : Gąsienica :D

Algorytm dynamiczny na tablicy N x w: A jakbyś posortował te liczby i dla każdej pozycji sprawdzał ile jest sum o wartości k-A[i] dla k od 0 do w, które są zawarte w prefiksie? Miałoby to zlozonosc O(N*w) zamiast O(2^N) w przypadku backtrackingu.

Autor tematu zapominał wspomnieć, że liczby w tabeli w tabeli są dodatnie(co założyłem w rozwiązaniu liniowo zachłannym), tych liczb jest mniej niż < 5*10^5. , a "w" może być bardzo duże w <10^9. Także wszelkie pseudowielomianowe dynamiki mają w koszcie "w" odpadają z miejsca. I na wejściu nie mamy zbioru, tylko ciąg, kolejność elementów wejściowych jest ważna, ale to nie wiele zmienia. Kwadraty po n też odpadają, po rozmiarze danych można się domyślić że maksymalnie liniowo logarytmiczne rozwiązanie dostanie maks punktów.

Także jak najbardziej najdłuższy podciąg spełniający ten warunek to jest O(n) wyznaczony za pomocą Gąsienicy :D

Podzbiory a sekwencja (zakładając że ciągła, najdłuższa czy spełniająca jakieś dodatkowe warunki) to są dwa różne zadania.
@Spine chodzi o sekwencję? Bo na to są gotowe algorytmy.

@vpiotr: Tak, chodzi o sekwencję.

Tylko nie ogarniałem, że można to zadanie zrobić w taki wyrafinowany sposób i zaczynałem od brute force'a...

Czyli w sumie wyszło pytanie XY.