Subconjuntos y conjunto potencia
Genere todos los subconjuntos de un conjunto mediante retroceso y máscaras de bits, gestionando los duplicados al ordenar y omitir elementos repetidos.
Subconjuntos y conjunto potencia es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 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.
Subconjuntos y conjunto potencia
El conjunto potencia de un conjunto S es la colección de todos los subconjuntos posibles de S, incluido el conjunto vacío y el propio S. Un conjunto de n elementos tiene exactamente 2ⁿ subconjuntos. Para [1, 2, 3], los 8 subconjuntos son: [], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]. Este es un problema combinatorio fundamental que aparece en preguntas de entrevistas sobre cómo encontrar todas las combinaciones, particiones o elecciones posibles.
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16Generación de subconjuntos mediante backtracking
Utilice la plantilla Elegir-Explorar-Deshacer. La decisión de diseño clave es añadir a los resultados el camino parcial actual en cada llamada recursiva inmediatamente (antes de elegir más elementos). De este modo, cada estado —vacío, parcial y completo— se captura como un subconjunto válido. Avance el índice start para considerar únicamente los elementos a la derecha del último elemento elegido, lo que garantiza que no haya duplicados y conserva el orden.
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]Enfoque de máscaras de bits
Una alternativa al backtracking son las máscaras de bits: cada subconjunto corresponde a un número de n bits, donde el bit i igual a 1 significa que el elemento i está incluido. Recorra los valores de 0 a 2ⁿ - 1 y, para cada número, extraiga los bits para construir el subconjunto. Es un enfoque iterativo, a menudo más rápido en la práctica y muy fácil de programar. Sin embargo, no se generaliza tan limpiamente a problemas con restricciones (como un límite de suma).
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # bit i is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differGeneración iterativa de subconjuntos
El enfoque iterativo construye el conjunto potencia elemento por elemento. Comience con [[] ] (el conjunto vacío). Para cada elemento nuevo, duplique todos los subconjuntos existentes y añada el elemento nuevo a cada duplicado. Después de procesar n elementos, el resultado contiene los 2ⁿ subconjuntos. Esto equivale a utilizar máscaras de bits, pero resulta más legible para quienes no están familiarizados con las operaciones a nivel de bits.
def subsets_iterative(nums):
result = [[]] # start with empty set
for num in nums:
# For each existing subset, create a new subset with num added
result += [subset + [num] for subset in result]
return result
print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Subconjuntos II: gestión de duplicados
Cuando la entrada contiene duplicados, el enfoque ingenuo genera subconjuntos duplicados. Para [1, 2, 2], las dos apariciones de 2 producirían [1, 2] de forma independiente. Solución: ordene primero el arreglo y, después, omita un candidato en el nivel actual si es igual al candidato anterior en ese mismo nivel. Concretamente, en el bucle: if i > start and nums[i] == nums[i-1]: continue.
def subsets_with_dups(nums):
nums.sort() # sort to group duplicates together
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(nums)):
# Skip duplicates at the same tree level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]] — no duplicate subsetsPor qué funciona el salto de duplicados
La condición i > start and nums[i] == nums[i-1] omite un duplicado únicamente en el mismo nivel de recursión (el mismo start). No impide seleccionar el mismo valor en distintas profundidades. Para [1, 2, 2]: en el nivel 0 incluimos el primer 2 (índice 1) y, después, en el nivel siguiente (start=2), incluimos el segundo 2 para formar [2, 2]. Sin embargo, si intentáramos incluir de nuevo el segundo 2 en el nivel 0, la condición lo detectaría y lo omitiría.
# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once
nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)
def subsets(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
def subsets_with_dups(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
print(len(subsets_with_dups([1,2,2])), 'unique subsets') # 6Subconjuntos de tamaño fijo (k-combinaciones)
Generar únicamente subconjuntos de tamaño exactamente igual a k (LeetCode 77: Combinations) añade una condición de terminación temprana: si los elementos restantes no pueden completar la ruta hasta alcanzar el tamaño k, se poda. La condición que permite podar es i > n - (k - len(path)): si no quedan suficientes elementos, se detiene el proceso de forma anticipada. Esto reduce significativamente el espacio de búsqueda en comparación con generar todos los subconjuntos y filtrarlos.
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
# Prune: need (k - len(path)) more elements from [start..n]
# At most (n - start + 1) elements remain
if n - start + 1 < k - len(path):
return # not enough elements left
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3))) # C(10,3) = 120Aplicaciones del conjunto potencia
El patrón del conjunto potencia aparece en muchas variantes de entrevistas: (1) Partición en dos subconjuntos iguales — comprobar si algún subconjunto suma total/2. (2) Máximo XOR de dos subconjuntos — probar todos los pares de subconjuntos. (3) Coste mínimo de elegir k elementos — enumerar los k-subconjuntos. Aunque la enumeración directa es exponencial, muchos de estos problemas admiten soluciones de programación dinámica una vez que se reconoce la estructura. Plantear el problema como un conjunto potencia ayuda a identificar el espacio de estados, incluso cuando después se optimiza.
def max_subset_sum(nums, k):
'''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
# Backtracking approach: enumerate all k-subsets
max_s = [float('-inf')]
def bt(start, path, curr_sum):
if len(path) == k:
max_s[0] = max(max_s[0], curr_sum)
return
remaining_spots = k - len(path)
for i in range(start, len(nums)):
if len(nums) - i < remaining_spots: break # prune
bt(i+1, path+[nums[i]], curr_sum+nums[i])
bt(0, [], 0)
return max_s[0]
# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
return sum(sorted(nums, reverse=True)[:k])
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3)) # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3)) # 20Comprobación de suma de subconjuntos
Suma de subconjuntos plantea la siguiente pregunta: ¿algún subconjunto del array suma un objetivo determinado? Puede resolverse mediante backtracking (tiempo exponencial) o programación dinámica (tiempo polinómico). La versión con backtracking es sencilla, pero deja de ser práctica con entradas grandes. La versión con programación dinámica (la tabla booleana dp[target+1]) es el enfoque preferido en las entrevistas. Comprender ambas permite explicar la diferencia: el backtracking obtiene todas las soluciones, mientras que la programación dinámica responde de forma eficiente al problema de decisión.
# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
def bt(start, remaining):
if remaining == 0: return True
if remaining < 0 or start == len(nums): return False
# Include nums[start]
if bt(start + 1, remaining - nums[start]): return True
# Exclude nums[start]
return bt(start + 1, remaining)
return bt(0, target)
# DP version: O(n * target) time
def subset_sum_dp(nums, target):
dp = {0}
for num in nums:
dp |= {s + num for s in dp}
return target in dp
print(subset_sum_bt([3, 1, 4, 1, 5], 6)) # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6)) # TrueComplejidad de enumerar subconjuntos
Generar todos los subconjuntos tiene una complejidad temporal inevitable de O(n × 2ⁿ): hay 2ⁿ subconjuntos, cada uno con un tamaño medio de n/2. Ningún algoritmo puede hacerlo mejor cuando se solicitan todos los subconjuntos. En problemas que piden un único subconjunto con una propiedad determinada (como la suma máxima), debe preferirse la programación dinámica o un algoritmo voraz. Idea clave para entrevistas: pregunte siempre si necesita enumerar todos los subconjuntos o simplemente comprobar si algún subconjunto cumple una condición; la respuesta determina si es aceptable un tiempo exponencial o si se necesita uno polinómico.
import time
def count_subsets(n):
nums = list(range(n))
result = []
def bt(start, path):
result.append(None) # count without storing
for i in range(start, len(nums)):
path.append(i); bt(i+1, path); path.pop()
bt(0, [])
return len(result)
for n in [10, 15, 20]:
start = time.time()
cnt = count_subsets(n)
elapsed = time.time() - start
print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')Comparación de los tres enfoques
Para generar todos los subconjuntos: Backtracking es el enfoque más generalizable, ya que se adapta fácilmente a duplicados y restricciones. El enmascaramiento de bits es conciso y rápido, pero está limitado a n ≤ 30 (por el tamaño del entero). El enfoque iterativo es intuitivo y evita la sobrecarga de la recursión. Los tres producen una salida de O(n × 2ⁿ). En una entrevista, el backtracking demuestra que comprende el proceso recursivo de toma de decisiones, que se generaliza a problemas más difíciles. Mencione los tres al analizar los distintos enfoques.
# All three approaches for [1,2,3]
nums = [1, 2, 3]
# 1. Backtracking
def bt(start, path, res):
res.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)
# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
for mask in range(1<<len(nums))]
# 3. Iterative
res3 = [[]]
for num in nums:
res3 += [s+[num] for s in res3]
print('All produce', len(nums)**2, '-ish subsets:',
len(res1), len(res2), len(res3)) # all 8Comprobación rápida
Compruebe 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 que: el backtracking genera todos los subconjuntos añadiendo cada ruta parcial a los resultados antes de continuar la exploración, los duplicados se gestionan ordenando los valores y omitiendo los repetidos en la misma profundidad de recursión mediante la condición i > start and nums[i] == nums[i-1], y el enmascaramiento de bits ofrece una alternativa iterativa concisa en la que cada subconjunto se corresponde con una máscara de bits única. A continuación abordaremos las permutaciones y las combinaciones, problemas de enumeración relacionados, pero con restricciones diferentes.
Preguntas frecuentes
¿La lección «Subconjuntos y conjunto potencia» es gratis?
Sí — el texto completo de «Subconjuntos y conjunto potencia» 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 «Subconjuntos y conjunto potencia»?
Genere todos los subconjuntos de un conjunto mediante retroceso y máscaras de bits, gestionando los duplicados al ordenar y omitir elementos repetidos. 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 2 de 4.
¿Cuánto tiempo toma la lección «Subconjuntos y conjunto potencia»?
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
- Plantilla de backtracking: elegir, explorar y deshacer
- Subconjuntos y conjunto potencia
- Permutaciones y combinaciones
- N reinas y propagación de restricciones