Subset Sum Problem
nums contiene enteros positivos y target es un entero positivo. ¿Puedes elegir algunos de los valores, usando cada posición como máximo una vez, para que sumen exactamente target? Devuelve true si puedes y false si ninguna combinación funciona.
Función
- numsinteger-array
- los valores positivos entre los que puedes elegir
- targetinteger
- la suma exacta que deben alcanzar los valores seleccionados
- Devuelveboolean
- true cuando algunos de los valores suman exactamente target, false en caso contrario
Restricciones
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
Ejemplos
- Entrada
- nums = [8, 3, 11, 5, 7]target = 15
- Salida
- true
- Explicación
- 8 + 7 = 15, así que la respuesta es
true. La selección 3 + 5 + 7 también funciona; una selección es suficiente.
- Entrada
- nums = [6, 9, 12, 15]target = 20
- Salida
- false
- Explicación
- Cada valor es múltiplo de 3, así que todas sus sumas también son múltiplos de 3. 20 no lo es, así que la respuesta es
false.
- Entrada
- nums = [4, 1, 2]target = 8
- Salida
- false
- Explicación
- Los tres valores juntos suman 4 + 1 + 2 = 7, que es menos que 8, así que ninguna selección puede alcanzarlo y la respuesta es
false.
Para ir más allá
Dos valores iguales en posiciones diferentes cuentan como selecciones distintas. ¿Cuántas selecciones dan como resultado target?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Empieza con
nums[0]. Si tu selección lo incluye, los otros valores deben sumartarget-nums[0]. Si no, deben sumartarget. Ambas son la misma pregunta en un arreglo más corto.Que los valores desde la posición
ien adelante puedan formar una sumardepende solo deiyr, yrnunca superatarget. Así que hay como máximo unas 200 × 10^4 preguntas diferentes, y cada una se puede responder una vez.Usa un booleano por cada suma desde 0 hasta
target, con solo la suma 0 alcanzable al principio. Añade los valores uno por uno: una sumaspasa a ser alcanzable cuandos-numya lo era. Actualiza las sumas de mayor a menor para que un valor no se use dos veces, y lee la respuesta entarget.
Solución
Una selección es un sí o un no para cada valor, así que 200 valores dan 2^200 selecciones. Sin embargo, solo importan las sumas hasta target ≤ 10^4. Registra qué sumas pueden formar los valores considerados hasta el momento: cada nuevo valor desplaza ese registro según su tamaño, y la búsqueda se convierte en una tabla de booleanos de n × target.
Tomar u omitir cada valor
Correcto, pero no termina con las pruebas más grandes
Intuición
canMake(i, remaining) pregunta si los valores desde la posición i en adelante pueden sumar exactamente remaining. Toma nums[i] si cabe, lo que deja remaining-nums[i] para el resto; si eso falla, lo omite. Cada elección es un camino, así que la búsqueda encuentra una elección siempre que exista.
Cuando no existe ninguna, recorre todas las posibilidades. Con 200 múltiplos de 3, cada uno como máximo 300, y un objetivo de 9998, ninguna elección funciona, pero cualquier grupo de 33 valores queda por debajo del objetivo: más de 10^37 caminos.
Algoritmo
- Escribe
canMake(i, remaining). - Un
remainingde 0 significa que la selección está completa: devuelve true. Si no quedan valores y aún queda algo por formar, devuelve false. - Si
nums[i] ≤ remainingycanMake(i+1, remaining-nums[i])es true, devuelve true. - De lo contrario, devuelve
canMake(i+1, remaining). - Devuelve
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)Completa una tabla de sumas alcanzables
Intuición
La recursión depende solo de una posición y de una suma restante entre 0 y target, y muchos caminos llegan al mismo par. En su lugar, rellena una tabla. made[i][s] es true cuando una selección de los primeros i valores suma exactamente s; la selección vacía da 0. Con num = nums[i-1], la suma s se obtiene si se obtenía sin num, made[i-1][s], o si num completa s-num, made[i-1][s-num], con s ≥ num.
En el primer ejemplo, después del 8 las sumas obtenidas son 0 y 8. El 3 añade 3 y 11, el 11 añade solo 14, el 5 añade 5 y 13, y 8 + 7 llega a 15. En los límites, la tabla tiene 201 × 10001 celdas, unas 2 × 10^6 operaciones.
Algoritmo
- Asigna a
madeun arreglo de n+1 filas por target+1 valores booleanos, todos false. Marcamade[0][0]como true para la selección vacía. - La fila
imaneja el valornum = nums[i-1], parai= 1 hasta n. - Para cada suma
sde 0 atarget, establecemade[i][s]comomade[i-1][s]. - Si
s ≥ numymade[i-1][s-num]es true, establecemade[i][s]como true. - Devuelve
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]Una fila de sumas, actualizada desde arriba
Intuición
Cada fila solo lee la fila anterior, así que un único array made[s] puede almacenarla. Sobrescríbela de abajo hacia arriba y un valor se reutiliza a sí mismo: con nums = [5] y el objetivo 10, s = 5 pasa a true; después, s = 10 lee esa entrada recién creada y usa el 5 dos veces.
Recorre desde target hacia abajo hasta num. La lectura en s-num llega a una celda inferior que el recorrido aún no ha sobrescrito, así que ve la fila de antes de num. Si una suma se puede formar, sigue pudiéndose formar, así que puedes parar en cuanto made[target] sea true. La memoria se reduce a target + 1 valores booleanos.
Algoritmo
- Empieza con un único arreglo de
target + 1valores booleanos, en el que solomade[0]sea verdadero. - Toma los valores en orden. Para cada
num, recorreshacia abajo, desdetargethastanum. - Siempre que
made[s-num]tenga el valor verdadero, marcamade[s]. - Detente y devuelve
trueen cuanto se marquemade[target]. - Si se agotan primero todos los valores, la respuesta es
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
Errores comunes y casos límite
- Un bucle ascendente sobre las sumas usa un valor dos veces:
[3]con el objetivo 9 devuelve true. - Olvidar
made[0] = true. Cada suma se construye a partir de la selección vacía, así que todas las respuestas resultan false. - Elegir primero los valores más grandes. Con
[6, 5, 5]y el objetivo 10, tomar 6 deja 4, que no se puede formar con ningún valor, mientras que 5 + 5 = 10. - Un valor mayor que
target, como en[10000]con el objetivo 1, no debe cambiar nada.num...targetde Swift detiene el programa y(num+1):(target+1)de R cuenta hacia atrás, así que comprueba primeronum ≤ target. - En Lua y R, la entrada para la suma
sse encuentra en el índices + 1.
Preguntas frecuentes4
¿Cuál es la complejidad temporal del problema de la suma de subconjuntos?
La tabla requiere un tiempo O(n × target), aproximadamente 2 × 10^6 pasos para 200 valores y un objetivo de 10^4, y una fila reduce la memoria a O(target). El costo depende del tamaño numérico del objetivo, por lo que el método es pseudo-polynomial e inútil para un objetivo como 10^18. En general, el problema de la suma de subconjuntos es NP-complete.
¿Qué relación hay entre Subset Sum, Partition Equal Subset Sum y la mochila 0/1?
La partición en subconjuntos de suma igual es Subset Sum con target = total / 2, después de comprobar que el total es par. Subset Sum es un problema de mochila 0/1 en el que cada valor es su propio peso y la mochila debe llenarse exactamente, así que la tabla contiene valores booleanos en lugar de los mejores valores.
¿Funciona la suma de subconjuntos con números negativos?
La idea funciona, el código de arriba no. Con números negativos, las sumas alcanzables van desde el total de los negativos hasta el total de los positivos, así que desplaza cada índice en función de esa suma mínima y rellena la fila de la misma manera. Ya no se puede omitir un valor mayor que la suma restante.
¿Cómo encuentras qué valores hacen que se cumpla el objetivo?
Conserva la tabla completa y empieza en made[n][target]. Avanza una fila a la vez: si made[i-1][s] es verdadero, no se necesitó nums[i-1]; de lo contrario, regístralo y réstalo de s. Te detienes en la suma 0 con una selección válida.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def isSubsetSum(nums, target):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
nums = [8, 3, 11, 5, 7] target = 15
Salida Esperada
true