Subset sum problem (${\sum }_{i\in S}{s}_i=t$)

Given finitely encoded nonnegative integers $s_i$ and target $t$, the subset sum problem asks whether some subset sums to $t$. Taking equal item weights and profits reduces it to testing whether a 0-1 knapsack problem with capacity $t$ attains value $t$.

For indexed occurrences with positive integer weights, let $D_i(t)$ record whether a subset of the first $i$ entries has sum $t$. The recurrence chooses whether the last occurrence is absent or present: $D_i(t)=D_{i-1}(t)\vee D_{i-1}(t-a_i)$, with an out-of-range term false. Initialize only sum zero true. Descending one-dimensional updates prevent reusing the current occurrence. Time is $O(ns)$ for target $s$ and space $O(s)$; positivity permits immediate rejection above the total. With weights bounded by $k$, the total is at most $nk$, making the bound polynomial in $n,k$.

A finite set $A$ of positive integers such that nonempty disjoint sets contained in $A$ have different sums, and the larger subset has the larger sum when their sizes differ. For $a_1<\cdots <a_n$, the size condition is equivalent to $a_1+\cdots +a_{k+1}>a_{n-k+1}+\cdots +a_n$ for $1\le k\le \lfloor (n-1)/2\rfloor$: the left side is the smallest possible sum of $k+1$ elements and the right side the largest sum of $k$ elements.