Smallest Missing Subset Sum

Given a list of positive integers, the task is to find the smallest positive integer that cannot be represented as the sum of any subset of the list. In other words, if A is the set of numbers, you need to find the minimum integer s such that

$$ s \notin \left\{ \sum_{i \in S} a_i : S \subseteq A \right\}.$$

This problem can be solved using a greedy algorithm: after sorting the array, maintain a running sum smallest representing all the values that can be formed from 1 to smallest - 1. If the next number is larger than smallest, then smallest is the answer. Otherwise, add that number to smallest and continue.

inputFormat

The input is read from standard input. The first line contains an integer T, the number of test cases. For each test case, the first line contains an integer N (the size of the array), and the second line contains N space-separated positive integers.

outputFormat

For each test case, output a single line containing the smallest positive integer that cannot be formed as the sum of any subset of the given array.## sample

2
3
1 2 2
4
1 2 3 10

6
7