Smallest Non-Obtainable Subsequence Sum

Given an array of positive integers, determine the smallest positive integer that cannot be obtained as the sum of any non-empty subsequence of the array. The approach involves sorting the array and then iteratively updating a candidate sum. Mathematically, if the sorted array is a[0], a[1], ..., a[n-1] and you have been able to form all sums in the range [1, S], then if a[i] > S+1, the answer is \(S+1\). Otherwise, update \(S\) as \(S + a[i]\) and continue.

inputFormat

The first line contains a single integer n representing the number of elements in the array. The second line contains n space-separated positive integers.

outputFormat

Output a single integer: the smallest positive integer that cannot be obtained as the sum of any non-empty subsequence of the array.

4
1 2 2 4

10