Smallest Missing Positive Subset Sum

Given an array of positive integers, determine the smallest positive integer that cannot be obtained as the sum of any subset of the array. Formally, you are to find the smallest integer \(s\) such that there is no subset of the given array whose elements sum to \(s\). This problem is inspired by the coin problem and the subset sum challenge.

Note: The array may contain duplicate numbers, and the elements are not necessarily in any order. The solution must use a greedy approach after sorting the array to achieve optimal performance.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) positive integers separated by spaces.

outputFormat

Output via standard output (stdout) a single integer, which is the smallest positive integer that cannot be represented as the sum of some subset of the input array.

4
1 1 1 1

5