Target Sum con signos positivos y negativos
Transforme el problema de asignación de target-sum en una mochila basada en la diferencia de sumas de subconjuntos y resuélvalo en tiempo O(n × sum).
Target Sum con signos positivos y negativos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
El problema Target Sum
Dado un array de enteros nums y un entero target, asigne un signo + o - a cada número para que la expresión resultante evalúe a target. Devuelva el número de formas distintas de hacerlo. Por ejemplo, con nums=[1,1,1,1,1] y target=3, hay 5 formas (elegir 4 elementos para que sean positivos y 1 negativo en posiciones diferentes).
Fuerza bruta: enumeración mediante DFS
Un enfoque DFS asigna a cada número el signo + o - y aplica recursión, devolviendo el recuento de nodos hoja que alcanzan target. Es correcto, pero tiene una complejidad temporal de O(2^n), es decir, exponencial. Para n=20, esto supone más de un millón de llamadas recursivas. Conviene mencionar primero el enfoque DFS y pasar rápidamente a la optimización con DP.
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5DFS con memoización
Añada memoización al DFS: el estado es (index, current_sum). Dado que current_sum puede variar desde -total hasta +total, hay O(n × total) estados únicos. Con memoización, el DFS se ejecuta en O(n × total) de tiempo y espacio. Este enfoque funciona y es válido en entrevistas, pero la DP basada en la transformación es más elegante y eficiente en cuanto a espacio.
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5Transformación matemática
Sea P el conjunto de números asignados a + y N el conjunto de los asignados a -. Entonces: sum(P) - sum(N) = target y sum(P) + sum(N) = total. Al sumar ambas ecuaciones: 2 × sum(P) = target + total, por lo que sum(P) = (target + total) / 2. El problema se reduce a: contar subconjuntos de nums cuya suma sea (target + total) / 2. Esta es exactamente la variante «count subsets» de la mochila 0/1.
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')Comprobaciones de validez antes de la DP
Antes de ejecutar la DP, compruebe: (1) target + total debe ser par (de lo contrario, sum(P) no es un entero, por lo que el problema es imposible); (2) abs(target) > total significa que el objetivo no se puede alcanzar, aunque todos los signos estén alineados. Si alguna comprobación falla, devuelva 0 inmediatamente. Estas comprobaciones gestionan los casos límite de forma sencilla, sin añadir condiciones especiales dentro del bucle de DP.
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5Recorrido de un ejemplo pequeño
Para nums=[1,1,1,1,1] y target=3: total=5, new_target=(3+5)//2=4. Contamos los subconjuntos cuya suma sea 4 a partir de [1,1,1,1,1]. Esto es C(5,4)=5 (elegir 4 unos para que sean positivos y el quinto sea negativo: 1+1+1+1-1=3). La DP devuelve correctamente 5. La transformación asigna de forma elegante el problema de asignación de signos a un problema estándar de conteo de subconjuntos.
Gestión de ceros en nums
Si nums contiene ceros, asignar + o - a un cero no cambia la suma. Cada cero duplica el número de asignaciones válidas. La DP lo gestiona de forma natural: al procesar num=0, el bucle interno range(new_target, -1, -1) recorre los valores desde new_target hasta 0, y dp[c] += dp[c - 0] = dp[c] duplica todas las sumas alcanzables. No se necesita ningún tratamiento especial si utiliza range(new_target, num-1, -1), que comienza en new_target y llega hasta 0 cuando num=0.
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1Comparación de complejidad
El DFS de fuerza bruta tiene una complejidad de O(2^n). El DFS con memoización tiene una complejidad de O(n × total) de tiempo y O(n × total) de espacio. La DP 1D basada en la transformación tiene una complejidad de O(n × new_target) de tiempo y O(new_target) de espacio, donde new_target ≤ total. La DP 1D utiliza mucho menos espacio que la memoización porque descarta la dimensión del índice mediante la transformación.
Relación con otros problemas de mochila
Target Sum conecta varios conceptos de mochila: comienza como un problema de asignación, se transforma en subset sum (como Partition Equal Subset Sum) y utiliza la misma plantilla de iteración hacia atrás de mochila 0/1, pero con conteo (como Coin Change II). Dominar estas conexiones le permite clasificar rápidamente problemas nuevos en entrevistas según su similitud estructural con patrones conocidos.
Casos límite y notas para entrevistas
Casos clave: (1) target = total: solo hay una forma (todos los signos son positivos); (2) target = -total: solo hay una forma (todos los signos son negativos); (3) target = 0 con todos los elementos iguales a cero: la respuesta es 2^n; (4) total muy grande pero n pequeño: el tamaño del array de DP 1D está limitado por total/2. En las entrevistas, explique verbalmente la transformación antes de programar: es la idea no evidente que distingue a los candidatos más sólidos.
Alternativa de DP 2D sin transformación
Sin la transformación, defina dp[i][s] como el número de formas de asignar signos a los primeros i números para alcanzar la suma s. La suma puede ser negativa, así que aplique un desplazamiento de total: utilice dp[i][s + total]. Esto requiere una tabla 2D de tamaño (n+1) × (2*total+1). Aunque es correcto, utiliza más espacio y es más difícil de programar rápidamente bajo la presión de una entrevista que la mochila 1D posterior a la transformación.
Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: Target Sum transforma la asignación de signos en el conteo de subconjuntos cuya suma es (target + total) / 2, la mochila 0/1 1D con iteración hacia atrás cuenta subconjuntos en O(n × new_target) de tiempo y O(new_target) de espacio y las comprobaciones tempranas de validez (suma impar, |target| > total) evitan ejecutar la DP innecesariamente. A continuación entraremos en el ámbito de las rutas más cortas con el algoritmo de Dijkstra y una cola de prioridad.
Preguntas frecuentes
¿La lección «Target Sum con signos positivos y negativos» es gratis?
Sí — el texto completo de «Target Sum con signos positivos y negativos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Target Sum con signos positivos y negativos»?
Transforme el problema de asignación de target-sum en una mochila basada en la diferencia de sumas de subconjuntos y resuélvalo en tiempo O(n × sum). Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Target Sum con signos positivos y negativos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Mochila 0/1 y optimización del espacio
- Mochila ilimitada y Coin Change II
- Suma de subconjunto con partición igual
- Target Sum con signos positivos y negativos