Enumeración de subconjuntos con bitmask
Recorra todos los subconjuntos mediante enteros
Enumeración de subconjuntos con bitmask es una lección gratuita de Coding 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 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.
Los subconjuntos como números
Cada subconjunto de n elementos se corresponde con un único entero. Cuente desde 0 y los bits de cada número elegirán exactamente qué elementos contiene. 🙂
Cuántos subconjuntos hay
Un conjunto de n elementos tiene 2^n subconjuntos. Por lo tanto, recorrer un entero desde 0 hasta 2^n menos 1 visita cada subconjunto exactamente una vez.
for mask in range(1 << n):
pass # mask is one subset1 << n es la cantidad
El desplazamiento 1 << n equivale a 2 elevado a n. Es la forma clara y rápida de escribir el límite superior del bucle que recorre los subconjuntos.
Leer el bit i
Para comprobar si el elemento i pertenece al subconjunto, compruebe su bit usando mask y 1 desplazado a la izquierda i posiciones. Un resultado distinto de cero indica que está incluido.
if mask & (1 << i):
take(items[i])Crear la lista de elementos elegidos
Recorra cada posición de bit y recopile los elementos cuyo bit esté activado. Así, una máscara se convierte en el subconjunto concreto que representa.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Conjuntos vacío y completo
La máscara 0 representa el subconjunto vacío, mientras que la máscara formada solo por unos representa el conjunto completo. Ambos casos se incluyen automáticamente porque el bucle recorre todos los valores.
Sumar un subconjunto
Dentro del bucle, sume los elementos elegidos para calcular la puntuación de cada subconjunto. Este es el núcleo de muchas soluciones pequeñas de fuerza bruta.
total = sum(v[i] for i in range(n) if mask & (1 << i))Contar los bits activados
El número de elementos elegidos es igual al popcount de la máscara. En Python, bin(mask).count('1') lo obtiene al instante.
size = bin(mask).count("1")Vigilar el límite
Como hay 2^n subconjuntos, esta técnica solo sirve para valores pequeños de n. En la práctica, alrededor de n igual a 20 es el límite para enumerarlos todos.
Por qué ganan las máscaras de bits
Un solo bucle de enteros reemplaza varios bucles anidados complicados, y las operaciones con bits son rápidas. El código queda breve, claro y fácil de probar.
Un patrón reutilizable
Recorra mask, descifre sus bits, calcule la puntuación del subconjunto y conserve el mejor resultado. Memorice esta plantilla y muchos problemas de subconjuntos se volverán rutinarios.
Comprobación rápida
Quiere comprobar si el elemento i está incluido en el subconjunto codificado por mask.
Resumen
Recorra mask desde 0 hasta 2^n menos 1, lea los bits con mask y 1 desplazado a la izquierda, y calcule la puntuación de cada subconjunto. Es una forma clara de aplicar fuerza bruta con valores pequeños de n. 🚀
Preguntas frecuentes
¿La lección «Enumeración de subconjuntos con bitmask» es gratis?
Sí — el texto completo de «Enumeración de subconjuntos con bitmask» 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 «Enumeración de subconjuntos con bitmask»?
Recorra todos los subconjuntos mediante enteros 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 3 de 4.
¿Cuánto tiempo toma la lección «Enumeración de subconjuntos con bitmask»?
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
- La fuerza bruta es una estrategia válida
- Enumere con itertools
- Enumeración de subconjuntos con bitmask
- Reduzca el espacio de búsqueda con inteligencia