Soma de subconjunto com partição igual

Dado um vetor não vazio de inteiros positivos nums, determine se é possível particioná-lo em dois subconjuntos com soma igual. Por exemplo, [1, 5, 11, 5] pode ser particionado em [1, 5, 5] e [11], ambos com soma 11. Se a soma total for ímpar, a resposta será imediatamente False. Caso contrário, precisamos encontrar um subconjunto cuja soma seja total_sum // 2 — um problema clássico de soma de subconjuntos.

A redução fundamental: se a soma total S for par e um subconjunto somar S//2, os elementos restantes automaticamente também somarão S//2. Portanto, Partição de Soma de Subconjuntos Iguais reduz-se a: algum subconjunto de números soma S//2? Esse é o problema clássico Soma de Subconjuntos, que é NP-completo e resolvemos com DP de mochila 0/1 em tempo O(n × S).

Defina um vetor booleano dp[c] em que dp[c] = True significa que existe um subconjunto cuja soma é exatamente c. Inicialize dp[0] = True (o subconjunto vazio soma 0) e todos os demais valores como False. Para cada número num, percorra a capacidade de target até num (iteração reversa da mochila 0/1) e defina dp[c] = dp[c] or dp[c - num].

Para [1, 5, 11, 5], total=22, alvo=11. Inicialmente, dp[0]=True. Depois de num=1: dp[1]=True. Depois de num=5: dp[5]=True, dp[6]=True. Depois de num=11: dp[11]=True (usando apenas 11). Já encontramos dp[11]=True — mas continuamos processando todos os números. Resposta final: dp[11]=True, portanto a partição é possível.

Podemos adicionar uma saída antecipada: se dp[target] se tornar True em qualquer momento, retorne True imediatamente. Isso pode acelerar drasticamente os cenários de melhor caso. Além disso, se algum elemento for igual ao alvo, podemos retornar True imediatamente. Se algum elemento exceder o alvo, ele não poderá fazer parte de nenhum subconjunto cuja soma seja o alvo, mas ainda precisamos verificar os demais.

Uma alternativa é manter um conjunto de somas alcançáveis. Comece com {0}. Para cada número, adicione-o a cada soma do conjunto atual: reachable = reachable | {s + num for s in reachable}. Filtre para manter apenas as somas que não ultrapassem o alvo. Ao final, verifique se target está no conjunto. Essa abordagem é intuitiva, mas pode usar mais memória e talvez seja mais lenta na prática.

A abordagem de DP é executada em tempo O(n × S), em que S = sum(nums), e usa espaço O(S) para o vetor booleano. Para as restrições do LeetCode (n ≤ 200, sum ≤ 20.000), isso representa no máximo 4.000.000 de operações — muito rápido. A abordagem com conjunto tem a mesma complexidade assintótica, mas pode ser mais lenta na prática devido à sobrecarga da construção do conjunto.

Um problema relacionado: conte o número de subconjuntos cuja soma seja um alvo. Altere o DP de booleano para inteiro: dp[c] = number of ways to reach sum c. Use adição em vez de OR: dp[c] += dp[c - num]. Inicialize dp[0] = 1. Use a mesma iteração reversa. Essa generalização mostra como o modelo de mochila se adapta a diferentes perguntas sobre subconjuntos.

Espere perguntas de acompanhamento: (1) E se for necessário retornar a partição propriamente dita? — isso exige DP 2D para reconstrução. (2) E se os elementos puderem ser negativos? — desloque o alvo ou use um dicionário em vez de um vetor. (3) Qual é a complexidade de tempo? — O(n × soma). (4) É possível melhorar se muitos números forem iguais? — sim, use contagem de frequências para reduzir o número de iterações externas. Mencione sempre essas compensações de forma proativa.

Partição de Soma de Subconjuntos Iguais é uma aplicação direta da mochila 0/1: os itens são os números, os pesos são iguais aos valores e a capacidade da mochila é igual ao alvo. Perguntamos se o valor máximo é igual ao alvo (viabilidade), não qual é o valor máximo. A iteração reversa é a mesma; apenas a operação muda de max para o booleano or. Reconhecer essa relação em uma entrevista demonstra forte capacidade de reconhecer padrões.

Casos extremos a tratar: (1) vetor de comprimento 1 — um único elemento não pode ser dividido, portanto é sempre False; (2) todos os elementos idênticos e quantidade par — pode funcionar ou não, dependendo dos valores individuais; (3) somas muito grandes — verifique as restrições antes de alocar o vetor de DP; (4) elementos maiores que o alvo — podem ser ignorados (nunca poderão fazer parte de um subconjunto cuja soma seja o alvo). A verificação do maior elemento como saída antecipada trata o caso (4) com eficiência.

Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.

Nesta lição, você aprendeu: Partição de Soma de Subconjuntos Iguais reduz-se ao problema da soma de subconjuntos com alvo = total//2, o DP 1D booleano dp[c] usa iteração reversa idêntica à da mochila 0/1 e a abordagem generaliza-se para contar subconjuntos, substituindo o OR booleano por adição de inteiros. Em seguida, abordaremos Soma-alvo, transformando atribuições de sinais em um problema de mochila baseado na diferença entre somas de subconjuntos.