Soma de Subconjuntos
Você tem em mãos um array de números inteiros positivos, não necessariamente distintos.
Vamos escolher alguns dos números no array, isto é, um subconjunto não vazio do array original. O valor de um subconjunto é a soma dos elementos contidos nele.
Qual é o menor valor de um subconjunto que não pode ser gerado?
Por exemplo, pegue o array [2, 1, 5]. Os seguintes subconjuntos pode ser formados: [1], [2], [5], [1, 2], [1, 5], [2, 5], [1, 2, 5]. Os seus valores são os seguintes: 1, 2, 5, 3, 6, 7, 8, respectivamente. O valor menor do subconjunto que não pode ser gerado, neste caso, é 4.
Entrada
A primeira linha contém um número T (1 ≤ T ≤ 1000), indicando que se seguirão T casos de teste.
Para cada teste, a primeira linha conterá um número N (1 ≤ N ≤ 10000), indicando a quantidade de números que existem no array. A linha seguinte conterá N inteiros positivos separados por espaços, entre 1 a 109.
Saída
Para cada caso de teste, imprima uma única linha, a resposta para o problema.
Exemplo de Entrada | Exemplo de Saída |
3
1 1 1 2 3 2 1 5 |
2
1 4 |