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?

• D.W.: 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.: 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.: Have you tried creating a dynamic programming algorithm? See cs.stackexchange.com/tags/dynamic-programming/info for a general approach.
• Arnav Borborah: @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.
• Arnav Borborah: 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).

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