Solução Soma de Subconjuntos

0 Flares Facebook 0 0 Flares ×

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:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: