Subset Sum Problem
nums contém inteiros positivos, e target é um inteiro positivo. Você consegue escolher alguns dos valores, usando cada posição no máximo uma vez, de modo que a soma seja exatamente target? Retorne true quando isso for possível e false quando nenhuma escolha funcionar.
Função
- numsinteger-array
- os valores positivos que você pode escolher
- targetinteger
- a soma exata que os valores escolhidos devem atingir
- Retornaboolean
- verdadeiro quando alguns dos valores somam exatamente target, falso caso contrário
Restrições
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
Exemplos
- Entrada
- nums = [8, 3, 11, 5, 7]target = 15
- Saída
- true
- Explicação
- 8 + 7 = 15, então a resposta é
true. A escolha 3 + 5 + 7 também funciona; uma escolha é suficiente.
- Entrada
- nums = [6, 9, 12, 15]target = 20
- Saída
- false
- Explicação
- Todo valor é múltiplo de 3, então toda soma deles também é múltiplo de 3. 20 não é, portanto a resposta é
false.
- Entrada
- nums = [4, 1, 2]target = 8
- Saída
- false
- Explicação
- Os três valores juntos somam 4 + 1 + 2 = 7, que é menor que 8, então nenhuma escolha consegue alcançá-lo e a resposta é
false.
Para ir além
Dois valores iguais em posições diferentes contam como escolhas diferentes. Quantas escolhas atingem target?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Comece com
nums[0]. Se sua escolha o incluir, os outros valores devem somartarget-nums[0]. Caso contrário, devem somartarget. Ambas são a mesma pergunta em um array menor.Se os valores a partir da posição
ipodem formar uma somardepende apenas deier, ernunca ultrapassatarget. Portanto, há no máximo cerca de 200 × 10^4 perguntas diferentes, e cada uma pode ser respondida uma vez.Use um booleano para cada soma de 0 até
target, com apenas a soma 0 alcançável inicialmente. Adicione os valores um por um: uma somasse torna alcançável quandos-numjá era. Atualize as somas da maior para a menor para que um valor não seja usado duas vezes, e leia a resposta emtarget.
Solução
Uma escolha é um sim ou não para cada valor, então 200 valores geram 2^200 escolhas. Porém, só importam as somas até target ≤ 10^4. Registre quais somas os valores vistos até agora podem formar: cada novo valor desloca esse registro pelo seu tamanho, e a busca se transforma em uma tabela de n × target valores booleanos.
Escolha ou pule cada valor
Correta, mas não termina nos maiores testes
Intuição
canMake(i, remaining) verifica se os valores a partir da posição i conseguem somar exatamente remaining. Escolha nums[i] quando ele couber; isso deixa remaining-nums[i] para o restante; se isso não funcionar, pule-o. Cada escolha é um caminho, então a busca encontra uma escolha sempre que ela existe.
Quando não existe nenhuma, ela percorre todas. Com 200 múltiplos de 3, cada um de no máximo 300, e um alvo de 9998, nenhuma escolha funciona, mas quaisquer 33 valores permanecem abaixo do alvo: mais de 10^37 caminhos.
Algoritmo
- Escreva
canMake(i, remaining). - Um
remainingigual a 0 significa que a seleção está completa: retorne true. Se não houver mais valores e ainda houver algo a formar, retorne false. - Se
nums[i] ≤ remainingecanMake(i+1, remaining-nums[i])for true, retorne true. - Caso contrário, retorne
canMake(i+1, remaining). - Retorne
canMake(0, target).
def isSubsetSum(nums, target):
n = len(nums)
# Can some of nums[i], nums[i+1], ... add up to exactly remaining?
def can_make(i, remaining):
if remaining == 0:
return True
if i == n:
return False
if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
return True # take nums[i]
return can_make(i + 1, remaining) # skip it
return can_make(0, target)Preencha uma tabela de somas alcançáveis
Intuição
A recursão depende apenas de uma posição e de uma soma restante entre 0 e target, e muitos caminhos chegam ao mesmo par. Preencha uma tabela. made[i][s] é verdadeiro quando uma seleção dos primeiros i valores soma exatamente s; a seleção vazia resulta em 0. Com num = nums[i-1], a soma s é possível se ela já era possível sem num, made[i-1][s], ou se num completa s-num, made[i-1][s-num], com s ≥ num.
No primeiro exemplo, depois do 8, as somas possíveis são 0 e 8. O 3 acrescenta 3 e 11, o 11 acrescenta apenas 14, o 5 acrescenta 5 e 13, e 8 + 7 alcança 15. Nos limites, a tabela tem 201 × 10001 células, cerca de 2 × 10^6 etapas.
Algoritmo
- Alocar
madecom n+1 linhas por target+1 valores booleanos, todos falsos. Marcarmade[0][0]como verdadeiro para a escolha vazia. - A linha
itrata do valornum = nums[i-1], parai= 1 até n. - Para cada soma
sde 0 atétarget, definirmade[i][s]comomade[i-1][s]. - Se
s ≥ numemade[i-1][s-num]for verdadeiro, definirmade[i][s]como verdadeiro. - Retornar
made[n][target].
def isSubsetSum(nums, target):
n = len(nums)
# made[i][s]: some of the first i values add up to exactly s
made = [[False] * (target + 1) for _ in range(n + 1)]
made[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
# leave num out, or put it in on top of a sum of s-num
made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
return made[n][target]Uma linha de somas, atualizada de cima para baixo
Intuição
Cada linha lê apenas a linha anterior, então um array made[s] pode armazená-la. Sobrescreva-o de baixo para cima e um valor alimentará a si mesmo: com nums = [5] e alvo 10, s = 5 se torna verdadeiro, então s = 10 lê essa entrada recém-criada, usando o 5 duas vezes.
Vá de target até num, em ordem decrescente. A leitura em s-num acessa uma célula inferior que a varredura ainda não reescreveu, então ela vê a linha anterior a num. Uma soma que pode ser formada continua podendo ser formada, então você pode parar assim que made[target] for verdadeiro. O uso de memória cai para target + 1 valores booleanos.
Algoritmo
- Comece com um único array de
target + 1valores booleanos, no qual apenasmade[0]é true. - Percorra os valores em ordem. Para cada
num, percorrasem ordem decrescente, detargetaténum. - Sempre que
made[s-num]for true, marquemade[s]. - Encerre com
trueassim quemade[target]for marcado. - Se todos os valores forem usados primeiro, a resposta será
false.
def isSubsetSum(nums, target):
# made[s]: some of the values seen so far add up to exactly s
made = [False] * (target + 1)
made[0] = True
for num in nums:
# Downward, so made[s - num] still ignores num
for s in range(target, num - 1, -1):
if made[s - num]:
made[s] = True
if made[target]:
return True
return False
Armadilhas e casos extremos
- Um loop crescente pelas somas usa um valor duas vezes:
[3]com alvo 9 responde verdadeiro. - Esquecer
made[0] = true. Toda soma se baseia na escolha vazia, então todas as respostas são falsas. - Escolher primeiro os maiores valores. Em
[6, 5, 5]com alvo 10, escolher 6 deixa 4, que não pode ser formado por nenhum valor, enquanto 5 + 5 = 10. - Um valor acima de
target, como em[10000]com alvo 1, não deve alterar nada. Onum...targetdo Swift interrompe o programa, e o(num+1):(target+1)do R conta para trás, então verifiquenum ≤ targetprimeiro. - Em Lua e R, a entrada para a soma
sfica no índices + 1.
Perguntas frequentes4
Qual é a complexidade de tempo do problema da soma de subconjuntos?
A tabela custa O(n × target) de tempo, cerca de 2 × 10^6 passos para 200 valores e um target de 10^4, e uma linha reduz a memória para O(target). O custo acompanha o tamanho numérico do target, então o método é pseudo-polinomial e inútil para um target como 10^18. Em geral, o problema da soma de subconjuntos é NP-completo.
Como o problema da soma de subconjuntos se relaciona com o problema de partição em subconjuntos de soma igual e com o problema da mochila 0/1?
Partição em subconjuntos de soma igual é o problema da soma de subconjuntos com target = total / 2, após verificar se o total é par. A soma de subconjuntos é um problema de mochila 0/1 em que cada valor é seu próprio peso e a mochila deve ser preenchida exatamente, então a tabela armazena valores booleanos em vez dos melhores valores.
A soma de subconjuntos funciona com números negativos?
A ideia funciona, o código acima não. Com números negativos, as somas alcançáveis vão do total dos negativos ao total dos positivos, então desloque cada índice por essa soma mínima e preencha a linha da mesma forma. Um valor maior que a soma restante não pode mais ser ignorado.
Como você encontra quais valores atingem o alvo?
Mantenha a tabela completa e comece em made[n][target]. Suba uma linha por vez: se made[i-1][s] for verdadeiro, nums[i-1] não foi necessário; caso contrário, registre-o e subtraia-o de s. Você para quando a soma chegar a 0, com uma escolha válida.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def isSubsetSum(nums, target):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
nums = [8, 3, 11, 5, 7] target = 15
Saída Esperada
true