Soma de Subconjuntos

subconjuntos.cpp

// URI - 1690
// Rogério Júnior
// O(n log n)

#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 10100

int t, n, vetor[MAXN];

int main(){
	
	scanf("%d", &t);
	
	// para cada caso
	while(t--){
		
		scanf("%d", &n);
		
		// salvo os números em vetor
		for(int i=0; i<n; i++) scanf("%d", &vetor[i]);
		
		// ordeno os elementos de vetor
		sort(vetor, vetor+n);
		
		// resp começa com 1
		long long int resp=1;
		
		// para cada elemento
		for(int i=0; i<n; i++){
			
			// se ele for maior que resp, não podemos formá-labs
			// e o algoritmo para
			if(vetor[i]>resp) break;
			
			// caso contrário, atualizamos o valor de resp
			else resp+=vetor[i];
		}
		
		// no fim, imprimimos o valor de resp
		printf("%lld\n", resp);
	}
	
	return 0;
}