# Smallest sum not obtainable using a subset of elements in array greater than the minimum element

I am solving a variation of the missing coin sum problem, modified to be as follows:

You have n coins with positive integer values. What is the smallest sum greater than the minimum coin in the array you cannot create using a subset of the coins?

Constraints:

$$1 \le n \le 2 \cdot 10^5$$

$$1 \le x_i \le 10^9$$

Input:

2 9 1 2 7

Output: 6

Input:

5 7 6 9

Output: 8

For the original problem (where the minimum sum does not have to be at least the minimum element in the array), there is a greedy algorithm that sorts the array and tracks the minimum sum not obtainable so far, adding successive elements to that sum provided that adding each element does not create a "gap" in the range of elements possible. In other words, an invariant is being maintained that for the value of $$s$$ at index $$i$$, all values until and including $$s - 1$$ can be constructed using elements up to index $$i - 1$$. If the $$a[i]$$ is greater than $$s$$, then $$s$$ cannot be constructed using a subset of the elements because:

1. $$a[i]$$ is itself greater than $$s$$, so it cannot be used alone nor added to any other subset of previous elements as that would be greater than the element itself.
2. Since $$s$$ is 1 more than the sum of $$a[1..i - 1]$$, $$s$$ cannot be created by any subset of those elements.

In that case, the value of $$s$$ is returned, since $$s$$ is the smallest value in the "gap" that is being constructed by the new element $$a[i]$$. If $$a[i]$$ is less than or equal to $$s$$, that shows that every element from 1 to and including $$s$$ can be created and that the new minimum unobtainable sum is the $$s + a[i]$$:

1. If $$a[i] = s$$, then $$s$$ is obtainable using $$a[i]$$ itself.
2. For all values $$[s + 1, s + a[i])$$, their values can be obtained by adding $$a[i]$$ to one of the previous subset sums. Adding $$a[i]$$ extends the range of sums and maintains the invariant.

For example in the first case, the algorithm runs as follows:

1. set $$s = 1$$
2. $$a[i] = 1$$, $$1 \le 1$$, so $$s = 2$$
3. $$a[i] = 2$$, $$2 \le 2$$, so $$s = 4$$
4. $$a[i] = 2$$, $$2 \le 4$$, so $$s = 6$$
5. $$a[i] = 7$$, $$7 \not\le 6$$, so return our value of $$s$$ as $$6$$.

This works in the first case, but does not in the second case, as the initial $$s$$ cannot be set to 1 (it has to be greater than the minimum element of 5 for our answer). I thought about setting it to the minimum element + 1, 6, but this would not work as the algorithm would assume that all values prior to 6 are possible to create, which is not true in this case. i.e

1. set $$s = 6$$
2. $$a[i] = 5, 5 \le 6, s = 11$$ which is already incorrect.

This is not the correct approach. How can I change my approach/algorithm entirely to find the correct minimum unobtainable sum?

• What does "using a subset of the coins that is greater than the minimum coin in the array" mean? What does it mean for a subset to be greater than a coin? The two are not comparable objects. You can compare two numbers, but not a set and a physical object. Please edit your post to clarify the problem statement.
– D.W.
Commented Aug 20 at 4:06
• I don't understand the greedy algorithm. Can you describe it in pseudocode? I don't understand what $s$ represents. How do you tell whether it creates a "gap"? I don't understand what is the "first case" and "second case".
– D.W.
Commented Aug 20 at 4:08
• Have you tried creating a dynamic programming algorithm? See cs.stackexchange.com/tags/dynamic-programming/info for a general approach.
– D.W.
Commented Aug 20 at 4:09
• @D.W. I've edited the question, hopefully it makes more sense. It was meant to say the "minimum unobtainable sum .. that is greater than the minimum coin". $s$ represents the minimum sum not obtainable by any subset of coins at an index $i$, following the loop invariant that all elements up to and including $s - 1$ can be created using some subset in $a[1..i - 1]$. stackoverflow.com/a/21073903/6525260 has a good explanation of the algorithm as well. Commented Aug 20 at 18:39
• Regarding dynamic programming, I haven't looked too deeply into it. I'm aware the original problem has a DP solution, though to tell the truth my knowledge of the topic isn't advanced enough to come up with one myself (yet). Commented Aug 20 at 18:41

There is a straightforward solution using dynamic programming. In particular, the pseudo-polynomial time algorithm for subset sum finds, for each $$s$$, whether there is a subset of coins that sum to $$s$$. You can then scan that array to find the first $$s$$ such that the answer is "no".