Soma de Subconjuntos e Particionamento
Alcance um alvo com um subconjunto escolhido.
Soma de Subconjuntos e Particionamento é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
A questão da soma de subconjuntos
Dado um conjunto de números e um alvo, algum subconjunto pode somar exatamente esse alvo? É uma mochila em que o valor é igual ao peso.
DP booleana, não valor
Aqui você acompanha a alcançabilidade, não um máximo. Seja dp[s] True quando algum subconjunto soma exatamente s.
dp = [False] * (target + 1)
dp[0] = TrueZero é sempre alcançável
O subconjunto vazio soma zero, portanto dp[0] começa como True. Todas as outras somas começam como False até que um número prove que são alcançáveis.
A transição
Para cada número, marque s como alcançável se s - num já era. Um número pode mudar muitas somas para True.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]Mais uma vez, para trás
Cada número é usado no máximo uma vez, então o laço interno percorre para trás, assim como na mochila 0/1. Percorrer para a frente reutilizaria um número.
Leia o veredito
Depois de processar todos os números, dp[target] responde à pergunta. True significa que existe um subconjunto válido; False significa que é impossível.
Conheça o problema da partição
O problema da partição pergunta: é possível dividir o vetor em duas partes de soma igual? Ele se reduz diretamente à soma de subconjuntos.
Divida o total ao meio
Se a soma total for ímpar, partes iguais serão impossíveis; portanto, responda não imediatamente. Caso contrário, o alvo será simplesmente total // 2.
total = sum(nums)
if total % 2:
return False
target = total // 2Reutilize a soma de subconjuntos
Agora basta verificar se um subconjunto alcança total // 2. Se uma metade atingir o alvo, o restante formará automaticamente a segunda metade correspondente.
A complexidade
O custo é da ordem de n vezes target, um limite pseudopolinomial. É rápido quando o alvo é pequeno e lento quando as somas são enormes.
Uma família de problemas
Soma de subconjuntos, particionamento e mochila 0/1 compartilham o mesmo mecanismo. Identifique o padrão de escolher ou deixar de lado e reutilize o mesmo laço.
Verificação rápida
Teste a redução para particionamento.
Recapitulação
Você resolveu a soma de subconjuntos com DP booleana e um laço de trás para frente, depois reduziu o particionamento a atingir o total // 2. O mesmo mecanismo, com novas possibilidades. ✅
Perguntas Frequentes
A aula “Soma de Subconjuntos e Particionamento” é grátis?
Sim — o texto completo de “Soma de Subconjuntos e Particionamento” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Soma de Subconjuntos e Particionamento”?
Alcance um alvo com um subconjunto escolhido. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Soma de Subconjuntos e Particionamento”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Mochila 0/1: Escolher ou Deixar
- Mochila com Espaço Otimizado
- DP de Mochila Ilimitada e Troco de Moedas
- Soma de Subconjuntos e Particionamento