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

Question

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?

Answer 1

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".