Soma-alvo com sinais positivos e negativos

Dado um vetor de inteiros nums e um inteiro target, atribua um sinal + ou - a cada número para que a expressão resultante tenha valor target. Retorne o número de maneiras distintas de fazer isso. Por exemplo, com nums=[1,1,1,1,1] e target=3, existem 5 maneiras (escolher 4 elementos para serem positivos e 1 para ser negativo, em posições diferentes).

Uma abordagem com DFS atribui + ou - a cada número e faz chamadas recursivas, retornando a contagem dos nós folha que alcançam target. Está correta, mas tem complexidade de tempo O(2^n) — exponencial. Para n=20, são mais de um milhão de chamadas recursivas. Vale a pena mencionar primeiro a abordagem com DFS e, em seguida, passar rapidamente à otimização com DP.

Adicione memoização à DFS: o estado é (index, current_sum). Como current_sum pode variar de -total a +total, há O(n × total) estados únicos. Com memoização, a DFS é executada em tempo e espaço O(n × total). Isso funciona e é válido em entrevistas, mas o DP baseado em transformação é mais elegante e eficiente em termos de espaço.

Seja P o conjunto dos números aos quais foi atribuído + e N o conjunto dos que receberam -. Então: sum(P) - sum(N) = target e sum(P) + sum(N) = total. Somando: 2 × sum(P) = target + total, portanto sum(P) = (target + total) / 2. O problema reduz-se a: conte os subconjuntos dos números cuja soma seja (target + total) / 2. Esta é exatamente a variante de “contagem de subconjuntos” da mochila 0/1.

Antes de executar o DP, verifique: (1) target + total deve ser par (caso contrário, sum(P) não é um inteiro — impossível); (2) abs(target) > total significa que o alvo não pode ser alcançado, mesmo que todos os sinais estejam alinhados. Se alguma verificação falhar, retorne 0 imediatamente. Essas verificações tratam os casos extremos de forma clara, sem condições especiais dentro do laço do DP.

Para nums=[1,1,1,1,1], target=3: total=5, new_target=(3+5)//2=4. Contamos subconjuntos cuja soma seja 4 em [1,1,1,1,1]. Isso é C(5,4)=5 (escolha quatro números 1 para serem positivos, e o quinto para ser negativo: 1+1+1+1-1=3). O DP retorna corretamente 5. A transformação mapeia elegantemente o problema de atribuição de sinais para um problema padrão de contagem de subconjuntos.

Se nums contiver zeros, atribuir + ou - a um zero não altera a soma. Cada zero duplica o número de atribuições válidas. O DP trata isso naturalmente: ao processar num=0, o laço interno range(new_target, -1, -1) vai de new_target até 0, e dp[c] += dp[c - 0] = dp[c] duplica todas as somas alcançáveis. Não é necessário nenhum tratamento especial se você usar range(new_target, num-1, -1), que começa em new_target e vai até 0 quando num=0.

A DFS de força bruta é O(2^n). A DFS com memoização é O(n × total) em tempo e O(n × total) em espaço. O DP 1D baseado na transformação é O(n × new_target) em tempo e O(new_target) em espaço, em que new_target ≤ total. O DP 1D usa significativamente menos espaço que a memoização porque descarta a dimensão do índice por meio da transformação.

Soma-alvo reúne vários conceitos de mochila: começa como um problema de atribuição, transforma-se em soma de subconjuntos (como Partição de Soma de Subconjuntos Iguais) e usa o mesmo modelo de iteração reversa da mochila 0/1, mas com contagem (como em Troco II). Dominar essas relações permite classificar rapidamente novos problemas em entrevistas pela semelhança estrutural com padrões conhecidos.

Casos principais: (1) target = total: apenas uma maneira (todos positivos); (2) target = -total: apenas uma maneira (todos negativos); (3) target = 0 com todos os elementos iguais a zero: a resposta é 2^n; (4) total muito grande, mas n pequeno — o tamanho do vetor de DP é limitado por total/2. Em entrevistas, explique verbalmente a transformação antes de programar — é a ideia não óbvia que diferencia candidatos fortes.

Sem a transformação, defina dp[i][s] = número de maneiras de atribuir sinais aos primeiros i números para alcançar a soma s. A soma pode ser negativa, então desloque-a por total: use dp[i][s + total]. Isso exige uma tabela 2D de tamanho (n+1) × (2*total+1). Embora correta, ela usa mais espaço e é mais difícil de programar rapidamente sob a pressão de uma entrevista do que a mochila 1D após a transformação.

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: Soma-alvo transforma a atribuição de sinais na contagem de subconjuntos cuja soma é (target + total) / 2, a iteração reversa da mochila 0/1 1D conta subconjuntos em tempo O(n × new_target) e espaço O(new_target) e verificações antecipadas de validade (soma ímpar, |target| > total) evitam a execução desnecessária do DP. Em seguida, entraremos no território dos caminhos mais curtos com o algoritmo de Dijkstra e uma fila de prioridade.