Informatik

Gegeben Zahlen $a_1,\dots,a_n$ und Zielwert $T$: Gibt es eine Teilmenge mit Summe $T$?

Subset Sum ist NP-vollständig, besitzt aber pseudo-polynomielle dynamische Programmierung.