we're given a set of naturals $S \equiv \{ x_i \}$ and we want to find $n \equiv \min \{ sum(T): T \subseteq S \}$, the smallest number that can't be written as a sum of elements from $S$.

§ By observation

• Key observation: If we sort the set $S$ as $s[1] \leq s[2] \leq \dots \leq s[n]$, then we must have $s[1] = 1$. For if not, then $1$ is the smallest nmber which cannot be written as a sum of elements.
• Next, if we think about the second number, it must be $s[2] = 2$. If not, we return $2$ as the answer.
• The third number $s[3]$ can be $3$. Interestingly, it can also be $4$, since we can write $3 = 1 + 2$, so we can skip $3$as an input.
• What about $s[4]$? If we had $[1 \leq 2 \leq 3]$ so far, then see that we can represent all numbers upto $6$. If we have $[1 \leq 2 \leq 4]$ so far, then we can represent all numbers upto $7$. Is it always true that given a "satisfactory" sorted array $A$ (to be defined recursively), we can always build numbers upto $\sum A$?
• The answer is yes. Suppose the array $A$ can represent numbers upto $\sum A$. Let's now append $r \equiv sum(A)+1$ into $A$. ( $r$ for result). Define B := append(A, r). We claim we can represent numbers $[1 \dots (r+\sum A)]$ using numbers from $B$. By induction hypothesis on A. We can represent $[1 \dots \sum A ]$ from $A$. We've added $r = \sum A + 1$ to this array. Since we can build numbers $[1\dots \sum A]$ from $A$, we can add $r$ to this to build the range $[r+1 \dots r + \sum A]$. In total, by not choosing $r$, we build the segment $[1 \dots \sum A ]$ and by choosing $r$ we build the segment $[\sum A + 1 \dots \sum A + r]$giving us the full segment $[1 \dots \sum A + r]$.

§ Take 2: code

• Input processing:

void main() {  int n;  cin >> n;  vector<ll> xs(n);  for (ll i = 0; i < n; ++i) {    cin >> xs[i];  }

• Sort to order array

  sort(xs.begin(), xs.end());

• Next define r as max sum seen so far.

  ll r = 0; // Σ_i=0^n xs[i]

• We can represent number $[0\dots r]$ What can $xs[i]$ be? If it is greater than $(r+1)$, then we have found a hole. If $xs[i] = r+1$, then we can already represent $[0\dots r]$. We now have $(r+1)$. By using the previous numbers, we can represent the sums $(r+1) + [0 \dots r]$, which is equal to $[r+1 \dots 2r+1]$.
• More generally, if $xs[i] < r+1$, we can represent $[0 \dots r]; [xs[i]+0, xs[i]+r]$.
• The condition that this will not leave a gap between $r$ and $xs[i]$ is to say that $xs[i]+0 \leq (r+1)$.

  for (ll i = 0; i < n; ++i) {    if (xs[i] <= r+1) {      // xs[i] can represent r+1.      // We can already represent [0..r]      // By adding, we can represent [0..r] + (xs[i]) = [xs[i]..r+xs[i]]      // Since xs[i] <= r+1, [xs[i]..r+xs[i]] <= [r+1, 2r+1].      // In total, we can represent [0..r] (not using xs[i]) and [<=r+1, <=2r+1]      // (by using xs[i]) So we can can be sure we won't miss numbers when going      // from [1..r] to [xs[i]<=r+1...] The largest number we can represent is      // [xs[i]+r].      r += xs[i]; // max number we can represent is previous max plus current    } else {      // xs[i] > r+1. We have a gap at r+1      cout << r + 1 << "\n";      return;    }  }  cout << r + 1 << "\n";}