# Subset-sum problemLast edited: 2026-02-05# 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