 Solution

Treat array entries as indexed occurrences, so equal numerical values may be selected independently. Put $S={\sum }_{j=1}^n{a}_j\le nk$. Reject $s<0$ or $s>S$. Define $D_i(t)$ to mean that some subset of the first $i$ indices sums to $t$. The base is $D_0(0)=\mathrm{True}$ and all other base entries are false. Considering whether index $i$ is selected givesOnly $0\le t\le s$ is needed, because all entries are positive. A one-dimensional implementation isDescending updates make both right-hand-side values belong to the previous list prefix: when updating $t$, the smaller location $t-a$ has not yet been updated for this entry. This prevents using the same occurrence repeatedly. Induction on the list prefix proves the recurrence and the returned answer.

The time is $O(n(s+1))\subseteq O(n^{2}k)$ for nonempty input with $k\ge 1$, and space is $O(s+1)\subseteq O(nk)$. More generally one may fill through $S$ and answer every target from the same table. For a two-way equal partition, reject odd $S$; otherwise ask for target $S/2$. A selected subset with that sum leaves its complement with the same sum. These are bounds polynomial in the numerical bound $k$; without that bound the method is pseudopolynomial in a binary-encoded unrestricted target.^[ref]