Suma de subconjuntos y partición
Alcance un objetivo con un subconjunto elegido
Suma de subconjuntos y partición 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.
La pregunta de la suma de subconjuntos
Dada una serie de números y un objetivo, ¿puede algún subconjunto sumar exactamente ese objetivo? Es una mochila en la que el valor es igual al peso.
DP booleana, no de valores
Aquí debe controlar la alcanzabilidad, no un máximo. Sea dp[s] True cuando algún subconjunto suma exactamente s.
dp = [False] * (target + 1)
dp[0] = TrueCero siempre es alcanzable
El subconjunto vacío suma cero, así que dp[0] comienza en True. Todas las demás sumas comienzan en False hasta que un número demuestre que son alcanzables.
La transición
Para cada número, marque s como alcanzable si s - num ya lo era. Un solo número puede convertir muchas sumas en True.
for num in nums:
for s in range(target, num - 1, -1):
dp[s] = dp[s] or dp[s - num]De nuevo hacia atrás
Cada número se usa como máximo una vez, así que el bucle interior avanza hacia atrás, igual que en la mochila 0/1. Hacia delante reutilizaría un número.
Lea el veredicto
Después de procesar todos los números, dp[target] responde la pregunta. True significa que existe un subconjunto válido; False significa que es imposible.
Entre en la partición
El problema de la partición pregunta: ¿puede dividir el arreglo en dos partes de suma igual? Se reduce directamente a la suma de subconjuntos.
Divida el total entre dos
Si la suma total es impar, las mitades iguales son imposibles, así que responda que no de inmediato. De lo contrario, el objetivo es simplemente total // 2.
total = sum(nums)
if total % 2:
return False
target = total // 2Reutilice la suma de subconjuntos
Ahora solo debe comprobar si un subconjunto alcanza total // 2. Si una mitad alcanza el objetivo, el resto forma automáticamente la segunda mitad correspondiente.
La complejidad
El coste es de orden n por objetivo, un límite seudopolinómico. Es rápido cuando el objetivo es pequeño y lento cuando las sumas son enormes.
Una familia de problemas
La suma de subconjuntos, la partición y la mochila 0/1 comparten un mismo motor. Identifique la estructura de elegir o dejar y podrá reutilizar el mismo bucle.
Comprobación rápida
Pruebe la reducción de partición.
Repaso
Ha resuelto la suma de subconjuntos con DP booleana y un bucle hacia atrás, y después ha reducido partición a alcanzar total // 2. El mismo motor, con nuevas ventajas. ✅
Preguntas frecuentes
¿La lección «Suma de subconjuntos y partición» es gratis?
Sí — el texto completo de «Suma de subconjuntos y partición» 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 «Suma de subconjuntos y partición»?
Alcance un objetivo con un subconjunto elegido 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 «Suma de subconjuntos y partición»?
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: elegir o dejar
- Mochila optimizada en espacio
- DP de mochila ilimitada y cambio de monedas
- Suma de subconjuntos y partición