Solução Soma de Subconjuntos

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

Vamos salvar a sequência no array $$vetor$$, e depois ordená-lo. Vamos agora processar ordenadamente cada um dos números do vetor. Seja $$resp$$ o menor inteiro que não conseguimos formar com os elementos que já temos. Antes de processar qualquer elemento, o valor de $$resp$$ é $$1$$, pois não temos elementos para formá-lo.

Agora, para cada elemento, observe o processamento do $$i$$-ésimo elemento do array. Se $$resp$$ é o menor elemento que não podemos formar, então conseguimos formar todas as somas de $$1$$ a $$resp-1$$. Se $$vetor[i] > resp$$, então não há como formarmos o valor de $$resp$$ usando elemento anteriores a $$i$$ (por definição de $$resp$$) nem com elemento a partir de $$i$$ (pois serão todos maiores que $$resp$$). Logo não preciso mais processar o resto do vetor e a resposta é $$resp$$.

Entretanto, se $$vetor[i]<resp$$, consigo formar todos os valores de $$resp$$ a $$vetor[i]+resp-1$$, pois sendo $$s$$ uma soma qualquer, seja $$x=s-vetor[i]$$. Logo para utilizarmos $$vetor[i]$$ em um subconjunto a fim de obtermos soma $$s$$, precisamos formar $$x$$ com outros, e só conseguimos formar $$1 \leq x <resp \Rightarrow resp \leq s < resp+s$$. Logo, o novo valor de $$resp$$ é $$resp+vetor[i]$$ e partiremos para a análise do próximo elemento. Segue o código para melhor entendimento:

https://gist.github.com/rogerioagjr/05d75fcab9824886cb4455aca049ca62