# Subset-sum problemLast edited: 2023-11-13# StatementSubset-sum problemGiven positive integers $a_1, \ldots, a_n$ and $t$, is there a subset $S \subset \{1, \ldots, n\}$ where$$\sum_{i \in S} a_i = t$$if such a subset exists output it, otherwise return no.# Solutions# TheorySubset-sum problem is in NPSubset-sum problem is NP-complete# Related problems