§ Smallest positive natural which can't be represented as sum of any subset of a set of naturals


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

§ By observation



§ Take 2: code



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


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


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


  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";
}