Target Sum
Se te da un arreglo nums de enteros no negativos y un entero target. Coloca un signo más o menos delante de cada número, conserva su orden y evalúa la expresión. Devuelve cuántas elecciones de signos hacen que la expresión sea igual a target. Cada una de las 2^n elecciones cuenta por separado, así que +0 y -0 son dos elecciones diferentes.
Función
- numsinteger-array
- los números, cada uno de los cuales recibe un signo
- targetinteger
- el valor que debe tener la expresión
- Devuelveinteger
- el número de opciones de signo cuya expresión es igual al objetivo
Restricciones
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000- The suma de
numses como máximo 1000. -1000 ≤ target ≤ 1000- La respuesta es como máximo 220, muy por debajo del límite de un entero con signo de 32 bits.
Ejemplos
- Entrada
- nums = [2, 1, 1]target = 2
- Salida
- 2
- Explicación
+2 +1 -1y+2 -1 +1son iguales a 2. Con un signo menos en el 2, lo máximo que puedes alcanzar es -2 + 1 + 1 = 0, así que ninguna otra opción funciona.
- Entrada
- nums = [0, 4, 4]target = 0
- Salida
- 4
- Explicación
- Los dos 4 necesitan signos opuestos,
+4 -4o-4 +4, y en ambos casos el 0 puede llevar cualquiera de los dos signos. Eso da 2 × 2 = 4 opciones.
- Entrada
- nums = [6, 3]target = 4
- Salida
- 0
- Explicación
- Los cuatro valores posibles son 9, 3, -3 y -9. Cambiar un signo modifica el total en el doble de ese número, así que todos los resultados son impares, como 6 + 3 = 9, y nunca se alcanza el objetivo par 4.
Para ir más allá
¿Puedes manejar hasta 40 números con valores de hasta 10^9, cuando ningún arreglo indexado por la suma cabe en la memoria?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Podrías probar ambos signos para cada número, lo que da
2^nexpresiones. Observa que muchos prefijos de signos diferentes conducen al mismo total acumulado y, a partir de ahí, se comportan exactamente igual.Llama
Pa la suma de los números que reciben un signo más yNa la suma de los números que reciben un signo menos. Sabes queP - N = targetyP + N = sum(nums). ¿Qué te dice eso sobreP?P = (sum + target) / 2, así que cuenta los subconjuntos denumscuya suma sea ese valor. Manténways[s], el número de subconjuntos que sumans, y actualízalo para cada número, recorriendosde mayor a menor. Devuelve 0 de inmediato cuandosum + targetsea impar o|target| > sum.
Solución
Cada número tiene dos signos, así que hay 2^n expresiones. Contar por posición y suma acumulada combina los prefijos de signos que llegan a la misma suma. Mejor aún, los números con signo positivo forman un subconjunto con una suma fija, por lo que el problema se convierte en contar los subconjuntos con una suma dada, en O(n × S) de tiempo, donde S es la suma de nums.
Prueba ambos signos para cada número
Correcto, pero no termina con las pruebas más grandes
Intuición
Recorre los números de izquierda a derecha llevando un total acumulado y bifurcándote dos veces en cada uno: súmalo o réstalo. Cuando todos los números tengan un signo, cuenta 1 si el total es igual a target. Cada elección de signo es exactamente un camino, así que las cantidades suman la respuesta.
Eso es una hoja por cada elección: 2^20 ≈ 10^6 hojas para 20 números, y cada número adicional duplica el trabajo.
Algoritmo
- Escribe
count(i, total), el número de formas de asignar signos anums[i..]cuando los números anteriores aiya sumantotal. - Si
i == n, devuelve 1 cuandototal == target; de lo contrario, 0. - De lo contrario, devuelve
count(i+1, total + nums[i]) + count(i+1, total - nums[i]). - La respuesta es
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)Memorizar según la posición y el total acumulado
Intuición
count(i, total) depende solo de i y total, no de los signos que produjeron el total. Con nums = [1, 1, 1, 1], los prefijos +1 -1 y -1 +1 llegan ambos al total 0 en la posición 2, así que la búsqueda desde ahí es la misma. Guarda cada resultado la primera vez y reutilízalo.
El total acumulado se mantiene entre -S y S, así que desplázalo en S para usarlo como índice: memo[i][total + S]. Hay como máximo n × (2S+1) estados, aproximadamente 4 × 10^4 para 20 números cuya suma es 1000, cada uno con un trabajo constante.
Algoritmo
- Calcula
S = sum(nums)y crea una tabla memo den × (2S+1)elementos, inicializada con -1. - En
count(i, total), devuelve el caso base eni == ncomo antes. - Si
memo[i][total + S]es -1, asígnalecount(i+1, total + nums[i]) + count(i+1, total - nums[i]). - Devuelve el valor almacenado y llama a
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)Cuenta los subconjuntos cuya suma sea (S + objetivo) / 2
Intuición
Sea P la suma de los números con signo más y N la del resto. Entonces P - N = target y P + N = S, así que 2P = S + target. Una elección de signos funciona exactamente cuando su grupo con signo más suma (S + target) / 2, y cada subconjunto de este tipo es una elección de signos.
ways[s] cuenta los subconjuntos de los números vistos hasta el momento cuya suma es s, empezando con ways[0] = 1. Para cada número x, un subconjunto que suma s puede omitir x o añadirlo a un subconjunto que suma s - x. Recorre los valores de s de mayor a menor, para que ways[s - x] conserve el valor que tenía antes de x y ningún número se use dos veces. Un 0 suma cada entrada a sí misma y duplica todos los recuentos: los dos signos de un cero. Eso supone n × goal sumas, como máximo 2 × 10^4.
Algoritmo
- Calcula
S = sum(nums). Si|target| > SoS + targetes impar, devuelve 0. - Establece
goal = (S + target) / 2, creawayscongoal + 1ceros y estableceways[0] = 1. - Para cada
xennums, desdegoalhastax, en orden descendente, sumaways[s - x]aways[s]. - Devuelve
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]
Errores comunes y casos límite
- Omitir la comprobación de paridad. Para
[6, 3]y el objetivo 4,(9 + 4) / 2se redondea hacia abajo a 6, y el subconjunto{6}da 1 en lugar de 0. - Omitir la comprobación del rango. Para
[1, 2, 3]y el objetivo -10,(6 - 10) / 2 = -2, un tamaño de matriz negativo. - Rellenar
waysde abajo hacia arriba. Después, un número se suma a un subconjunto que ya lo usa:[1, 3]con el objetivo 2 da 2 en lugar de 1. - Tratar un cero como una opción.
[0, 0, 0, 1, 0, 0]con el objetivo -1 tiene 32 respuestas, una por cada patrón de signos de los cinco ceros. - Usar un total acumulado negativo como índice de una memoria caché. Desplaza cada total en
So usa un mapa hash.
Preguntas frecuentes3
¿Qué relación tiene Target Sum con el problema de la suma de subconjuntos?
Los números con signo positivo deben sumar (S + target) / 2, así que la respuesta es el número de subconjuntos de nums con esa suma. Cualquier DP para contar sumas de subconjuntos lo resuelve una vez que añades dos comprobaciones: el valor debe ser un número entero y |target| no debe superar S.
¿Cuál es la complejidad temporal de Target Sum?
La programación dinámica de conteo de subconjuntos se ejecuta en tiempo O(n × S) con memoria O(S), donde S es la suma de nums. La recursión con memorización tiene el mismo tiempo, pero una tabla de n × (2S+1). Probar cada signo requiere O(2^n).
¿Se puede resolver Target Sum con un mapa hash de sumas acumuladas?
Sí. Asigna a cada suma acumulada alcanzable el número de prefijos de signos que llegan a ella, empezando con {0: 1}, y construye el siguiente mapa a partir de total + x y total - x para cada número. La respuesta es el recuento en target. Es la recursión con memoización ejecutada hacia delante, en el mismo tiempo O(n × S).
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def findTargetSumWays(nums, target):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
nums = [2, 1, 1] target = 2
Salida Esperada
2