When is splitting a collection coins two ways NP-complete? Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters).  In the first two problems, we want to know whether it is possible to divide the money in the jar equally between two people; in the third one, we're satisfied if the money can be divided almost equally.  What is the complexity of these problems?


$D = \{1, 2, 4, 8, \dots\}$.
$D = \{1, 2, 3, 4, \dots\}$.
$D = \{1, 2, 3, 4, \dots\}$ but we only require the two people to be given amounts $x$ and $y$, respectively, satisfying $|x-y|&lt; 10$.


My main question is what sets $D$ lead to the problem being in P and what makes it NP-complete.
Problem 2 is the same as the NP-complete problem PARTITION. Problem 3 is also NP-complete, since we can always arrange all denominations to be multiples of 10 cents.

The most interesting case is Problem 1. If the jar contains in total $2S$ cents, then we are looking for a subset of the jar summing to $S$. If $S$ is odd then there is no solution unless the jar contains a 1 cent coin, in which case we take one such coin and put it aside (it forms part of the solution), and update the target sum to $S-1$. Is $S$ is even we do nothing. In both cases, the new target sum is even. The number of 1 cent coins which appear in a solution must be even, and so we can group the 1 cent coins in pairs, replacing them with 2 cent coins (if there is an odd number, we just throws the odd one out). Now we repeat the same procedure with the 2 cent coins, the 4 cent coins, and so on, until we either reach the target sum or find out that the target sum is not reachable. This algorithm runs in polynomial time.