Smallest Unrepresentable Sum

Given a list of positive integers, your task is to determine the smallest positive integer that cannot be represented as the sum of any subset of the given list. In other words, if we define \(S\) as the set of all possible subset sums, you need to find the smallest integer \(m\) such that \(m \notin S\).

The idea behind the solution is to first sort the array. Then, by maintaining a running sum \(smallest\) (initialized to 1), we can check for each number in the sorted list: if the number is greater than \(smallest\), then \(smallest\) is the answer because all values below \(smallest\) can be formed from previous numbers. Otherwise, add the current number to \(smallest\) and continue.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) denoting the number of elements in the list.
• The second line contains \(n\) space-separated positive integers.

outputFormat

Output a single integer, which is the smallest positive integer that cannot be represented as the sum of any subset of the input list.

4
1 2 2 5

11