Given a positive integer $n$, we construct a multiset $S$ which contains only integers from $1$ to $n$, with each appearing at least once. Determine the values of $n$ for which any such set $S$ whose elements have an even sum can be partitioned into two subsets each with the same sum.
This is related to the Partition problem which is known to be NP-hard. Further, I'd be interested to know if there are any sufficient conditions for some multiset to be able to be partitioned into two subsets of equal sum. Some obvious necessary conditions include the sum being even, and the largest element being less than half the sum.