Suma de subconjunto con partición igual
Reformule el problema de partición como una mochila 0/1 con objetivo igual a la mitad de la suma total, detectando la viabilidad con un array booleano de PD.
Suma de subconjunto con partición igual es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 3 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 DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Planteamiento del problema
Dado un arreglo no vacío de enteros positivos nums, determine si puede dividirlo en dos subconjuntos con la misma suma. Por ejemplo, [1, 5, 11, 5] se puede dividir en [1, 5, 5] y [11], ambos con suma 11. Si la suma total es impar, la respuesta es inmediatamente False. De lo contrario, debemos encontrar un subconjunto cuya suma sea total_sum // 2: un problema clásico de subset sum.
Reducción a Subset Sum
La reducción clave: si la suma total S es par y un subconjunto suma S//2, los elementos restantes también suman automáticamente S//2. Por tanto, Partition Equal Subset Sum se reduce a: ¿algún subconjunto de nums suma S//2? Este es el problema clásico NP-completo Subset Sum, que resolvemos mediante DP de mochila 0/1 en O(n × S) de tiempo.
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False # odd sum: impossible
target = total // 2
# Now: does any subset of nums sum to target?Array booleano de DP
Defina un array booleano dp[c] donde dp[c] = True significa que existe un subconjunto cuya suma es exactamente c. Inicialice dp[0] = True (el subconjunto vacío suma 0) y todos los demás valores en False. Para cada número num, recorra la capacidad desde target hasta num (recorrido hacia atrás de la mochila 0/1) y establezca dp[c] = dp[c] or dp[c - num].
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1): # backward: 0/1 knapsack
dp[c] = dp[c] or dp[c - num]
return dp[target]
print(canPartition([1, 5, 11, 5])) # True
print(canPartition([1, 2, 3, 5])) # FalseRecorrido del ejemplo
Para [1, 5, 11, 5], total=22, target=11. Inicialmente, dp[0]=True. Después de num=1: dp[1]=True. Después de num=5: dp[5]=True, dp[6]=True. Después de num=11: dp[11]=True (usando únicamente el 11). Ya hemos encontrado dp[11]=True, pero continuamos procesando todos los números. Respuesta final: dp[11]=True, por lo que la partición es posible.
Optimización mediante terminación anticipada
Podemos añadir una salida anticipada: si dp[target] se convierte en True en cualquier momento, devuelva inmediatamente True. Esto puede acelerar drásticamente los casos más favorables. Además, si algún elemento individual es igual a target, podemos devolver True inmediatamente. Si algún elemento individual supera target, no puede formar parte de ningún subconjunto cuya suma sea target, pero aún debemos comprobar el resto.
def canPartition_fast(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
if max(nums) > target: # any element > target makes it impossible
return False
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for c in range(target, num - 1, -1):
dp[c] = dp[c] or dp[c - num]
if dp[target]:
return True # early exit
return dp[target]
print(canPartition_fast([1, 5, 11, 5])) # TrueUso de un set de Python en lugar de un array de DP
Una alternativa consiste en mantener un conjunto de sumas alcanzables. Comience con {0}. Para cada número, añádalo a cada suma del conjunto actual: reachable = reachable | {s + num for s in reachable}. Filtre el conjunto para conservar únicamente las sumas que no superen target. Al final, compruebe si target está en el conjunto. Este enfoque es intuitivo, pero puede utilizar más memoria y ser más lento en la práctica.
def canPartition_set(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
reachable = {0}
for num in nums:
reachable = {s + num for s in reachable if s + num <= target} | reachable
return target in reachable
print(canPartition_set([1, 5, 11, 5])) # TrueAnálisis de complejidad
El enfoque de DP se ejecuta en O(n × S) de tiempo, donde S = sum(nums), y utiliza O(S) de espacio para el array booleano. Con las restricciones de LeetCode (n ≤ 200, sum ≤ 20,000), esto supone como máximo 4.000.000 de operaciones, una cantidad muy pequeña. El enfoque basado en sets tiene la misma complejidad asintótica, pero puede ser más lento en la práctica debido al coste de construir los sets.
Generalización: contar subconjuntos con una suma
Un problema relacionado consiste en contar el número de subconjuntos cuya suma sea un objetivo. Cambie la DP de booleana a entera: dp[c] = number of ways to reach sum c. Use la suma en lugar de OR: dp[c] += dp[c - num]. Inicialice dp[0] = 1. Mantenga la misma iteración hacia atrás. Esta generalización muestra cómo adaptar la plantilla de mochila a distintas preguntas sobre subconjuntos.
def count_subsets(nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for num in nums:
for c in range(target, num - 1, -1):
dp[c] += dp[c - num]
return dp[target]
print(count_subsets([1, 1, 1, 1, 1], 3)) # 10 (C(5,3))Preguntas de seguimiento habituales en entrevistas
Espere preguntas de seguimiento: (1) ¿Qué ocurre si necesita devolver la partición real? — requiere una DP 2D para reconstruirla. (2) ¿Qué ocurre si los elementos pueden ser negativos? — desplace target o utilice un diccionario en lugar de un array. (3) ¿Cuál es la complejidad temporal? — O(n × sum). (4) ¿Se puede mejorar si muchos números son iguales? — sí, utilice un conteo de frecuencias para reducir el número de iteraciones externas. Mencione siempre estas ventajas y desventajas de forma proactiva.
Relación con la mochila 0/1
Partition Equal Subset Sum es una aplicación directa de la mochila 0/1: los elementos son los números, los pesos son iguales a los valores y la capacidad de la mochila es target. Preguntamos si el valor máximo es igual a target (factibilidad), no cuál es el valor máximo. La iteración hacia atrás es la misma; solo cambia la operación, de max a or booleano. Reconocer esta relación en una entrevista demuestra una gran capacidad para identificar patrones.
Casos límite
Casos límite que debe gestionar: (1) array de longitud 1: un solo elemento no se puede dividir, por lo que siempre es False; (2) todos los elementos son idénticos y su cantidad es par: puede funcionar o no, según los valores individuales; (3) sumas muy grandes: compruebe las restricciones antes de asignar el array de DP; (4) elementos mayores que target: se pueden omitir, ya que nunca pueden formar parte de un subconjunto cuya suma sea target. La comprobación del elemento máximo como salida anticipada gestiona el caso (4) de forma eficiente.
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: Partition Equal Subset Sum se reduce a subset-sum con target = total//2, la DP booleana 1D dp[c] utiliza una iteración hacia atrás idéntica a la de la mochila 0/1 y el enfoque se generaliza al conteo de subconjuntos al sustituir OR booleano por suma de enteros. A continuación abordaremos Target Sum, transformando las asignaciones de signos en un problema de mochila basado en la diferencia de sumas de subconjuntos.
Preguntas frecuentes
¿La lección «Suma de subconjunto con partición igual» es gratis?
Sí — el texto completo de «Suma de subconjunto con partición igual» 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 DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Suma de subconjunto con partición igual»?
Reformule el problema de partición como una mochila 0/1 con objetivo igual a la mitad de la suma total, detectando la viabilidad con un array booleano de PD. Practicas DSA 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 DSA Interview Prep?
No se requiere experiencia previa. DSA 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 3 de 4.
¿Cuánto tiempo toma la lección «Suma de subconjunto con partición igual»?
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 DSA Interview Prep?
Sí. Cada lección de DSA 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