Target Sum
Você recebe um array nums de inteiros não negativos e um inteiro target. Coloque um sinal de mais ou de menos na frente de cada número, mantenha a ordem e avalie a expressão. Retorne quantas escolhas de sinais fazem a expressão ser igual a target. Cada uma das 2^n escolhas conta individualmente, então +0 e -0 são duas escolhas diferentes.
Função
- numsinteger-array
- os números, cada um dos quais recebe um sinal
- targetinteger
- o valor ao qual a expressão deve ser igual
- Retornainteger
- o número de escolhas de sinal cuja expressão é igual ao alvo
Restrições
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000- A soma de
numsé no máximo 1000. -1000 ≤ target ≤ 1000- A resposta é, no máximo, 220, bem abaixo do limite de um inteiro com sinal de 32 bits.
Exemplos
- Entrada
- nums = [2, 1, 1]target = 2
- Saída
- 2
- Explicação
+2 +1 -1e+2 -1 +1ambos são iguais a 2. Com um sinal de menos no 2, o máximo que você pode alcançar é -2 + 1 + 1 = 0, então nenhuma outra escolha funciona.
- Entrada
- nums = [0, 4, 4]target = 0
- Saída
- 4
- Explicação
- Os dois 4 precisam ter sinais opostos,
+4 -4ou-4 +4, e, em ambos os casos, o 0 pode ter qualquer um dos sinais. Isso resulta em 2 × 2 = 4 possibilidades.
- Entrada
- nums = [6, 3]target = 4
- Saída
- 0
- Explicação
- Os quatro valores possíveis são 9, 3, -3 e -9. Inverter um sinal altera o total em duas vezes esse número, então todo resultado é ímpar, como 6 + 3 = 9, e o alvo par 4 nunca é alcançado.
Para ir além
Você consegue lidar com até 40 números com valores de até 10^9, quando nenhum array indexado pela soma cabe na memória?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Você poderia tentar ambos os sinais para cada número, o que resulta em
2^nexpressões. Observe que muitos prefixos de sinais diferentes levam ao mesmo total acumulado e, a partir daí, comportam-se exatamente da mesma maneira.Chame de
Pa soma dos números que recebem um sinal de mais e deNa soma dos números que recebem um sinal de menos. Você sabe queP - N = targeteP + N = sum(nums). O que isso diz sobreP?P = (sum + target) / 2, então conte os subconjuntos denumscuja soma seja esse valor. Mantenhaways[s], o número de subconjuntos que alcançams, e atualize-o para cada número, começando pelo maiorse seguindo em ordem decrescente. Retorne 0 imediatamente quandosum + targetfor ímpar ou|target| > sum.
Solução
Cada número tem dois sinais, então há 2^n expressões. Contar por posição e soma acumulada combina prefixos de sinais que chegam à mesma soma. Melhor ainda, os números com sinal de mais formam um subconjunto com uma soma fixa, então o problema se torna contar subconjuntos com uma determinada soma, em O(n × S) de tempo, onde S é a soma de nums.
Experimente ambos os sinais para cada número
Correta, mas não termina nos maiores testes
Intuição
Percorra os números da esquerda para a direita com um total acumulado e faça duas escolhas para cada um: somá-lo ou subtraí-lo. Quando todos os números tiverem um sinal, conte 1 se o total for igual a target. Cada escolha de sinal corresponde exatamente a um caminho, então a soma das contagens é a resposta.
Isso significa uma folha por escolha: 2^20 ≈ 10^6 folhas para 20 números, e cada número adicional dobra o trabalho.
Algoritmo
- Escreva
count(i, total), o número de maneiras de atribuir sinais anums[i..]quando os números anteriores aijá somamtotal. - Se
i == n, retorne 1 quandototal == target; caso contrário, retorne 0. - Caso contrário, retorne
count(i+1, total + nums[i]) + count(i+1, total - nums[i]). - A resposta é
count(0, 0).
def findTargetSumWays(nums, target):
n = len(nums)
def count(i, total):
# Ways to sign nums[i:] so that the whole expression ends at target
if i == n:
return 1 if total == target else 0
return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return count(0, 0)Memoize na posição e no total acumulado
Intuição
count(i, total) depende apenas de i e total, não dos sinais que produziram o total. Com nums = [1, 1, 1, 1], os prefixos +1 -1 e -1 +1 chegam ambos ao total 0 na posição 2, então a busca a partir daí é a mesma. Armazene cada resultado na primeira vez e reutilize-o.
O total acumulado permanece entre -S e S, então some S a ele para usá-lo como índice: memo[i][total + S]. Há no máximo n × (2S+1) estados, cerca de 4 × 10^4 para 20 números cuja soma é 1000, cada um com trabalho constante.
Algoritmo
- Calcule
S = sum(nums)e crie uma memo den × (2S+1)preenchida com -1. - Em
count(i, total), retorne o caso base emi == n, como antes. - Se
memo[i][total + S]for -1, preencha-o comcount(i+1, total + nums[i]) + count(i+1, total - nums[i]). - Retorne o valor armazenado e chame
count(0, 0).
def findTargetSumWays(nums, target):
n = len(nums)
whole = sum(nums)
# memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
memo = [[-1] * (2 * whole + 1) for _ in range(n)]
def count(i, total):
if i == n:
return 1 if total == target else 0
if memo[i][total + whole] == -1:
memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return memo[i][total + whole]
return count(0, 0)Conte os subconjuntos cuja soma é igual a (S + target) / 2
Intuição
Seja P a soma dos números com sinal de mais e N a soma dos demais. Então P - N = target e P + N = S, portanto 2P = S + target. Uma escolha de sinais funciona exatamente quando seu grupo de sinais de mais soma (S + target) / 2, e cada subconjunto desse tipo corresponde a uma escolha de sinais.
ways[s] conta os subconjuntos dos números vistos até agora cuja soma é s, começando com ways[0] = 1. Para cada número x, um subconjunto que chega a s ou não inclui x, ou o adiciona a um subconjunto que chega a s - x. Percorra os valores de s do maior para o menor, para que ways[s - x] ainda mantenha o valor de antes de x e nenhum número seja usado duas vezes. Um 0 soma cada entrada a si mesma, dobrando todas as contagens: os dois sinais de um zero. Isso resulta em n × goal adições, no máximo 2 × 10^4.
Algoritmo
- Calcule
S = sum(nums). Se|target| > SouS + targetfor ímpar, retorne 0. - Defina
goal = (S + target) / 2, criewayscomgoal + 1zeros e definaways[0] = 1. - Para cada
xemnums, parasdegoalatéx, someways[s - x]aways[s]. - Retorne
ways[goal].
def findTargetSumWays(nums, target):
whole = sum(nums)
# plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
if abs(target) > whole or (whole + target) % 2 == 1:
return 0
goal = (whole + target) // 2
# ways[s]: how many subsets of the values seen so far add up to s
ways = [0] * (goal + 1)
ways[0] = 1
for x in nums:
# From the top down, so each value is used at most once
for s in range(goal, x - 1, -1):
ways[s] += ways[s - x]
return ways[goal]
Armadilhas e casos extremos
- Pular a verificação de paridade. Para
[6, 3]e o alvo 4,(9 + 4) / 2é arredondado para baixo para 6, e o subconjunto{6}resulta em 1 em vez de 0. - Pular a verificação do intervalo. Para
[1, 2, 3]e o alvo -10,(6 - 10) / 2 = -2, um tamanho de array negativo. - Preencher
waysde baixo para cima. Assim, um número passa a fazer parte de um subconjunto que já o utiliza:[1, 3]com alvo 2 resulta em 2 em vez de 1. - Tratar um zero como uma opção.
[0, 0, 0, 1, 0, 0]com alvo -1 tem 32 respostas, uma para cada padrão de sinais dos cinco zeros. - Usar um total acumulado negativo como índice em uma tabela de memoização. Desloque cada total em
Sou use um mapa hash.
Perguntas frequentes3
Como Target Sum está relacionado ao problema da soma de subconjuntos?
Os números com sinal de mais devem somar (S + target) / 2, então a resposta é o número de subconjuntos de nums com essa soma. Qualquer DP de contagem de somas de subconjuntos resolve isso depois que você adiciona duas verificações: o valor deve ser um número inteiro, e |target| não pode exceder S.
Qual é a complexidade de tempo do Target Sum?
A programação dinâmica de contagem de subconjuntos é executada em O(n × S) de tempo e usa O(S) de memória, em que S é a soma de nums. A recursão com memoização tem o mesmo tempo, mas usa uma tabela de n × (2S+1). Tentar cada sinal leva O(2^n).
É possível resolver Target Sum com um mapa hash de totais acumulados?
Sim. Associe cada total acumulado alcançável ao número de prefixos de sinais que chegam até ele, começando com {0: 1}, e construa o próximo mapa a partir de total + x e total - x para cada número. A resposta é a contagem em target. É a recursão com memoização executada para a frente, no mesmo tempo O(n × S).
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def findTargetSumWays(nums, target):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
nums = [2, 1, 1] target = 2
Saída Esperada
2