Saltar al contenido

Subconjuntos

Lección 2 de 5 · 5 min

Subconjuntos

Paso 1 de 7

Un subconjunto es una respuesta de sí o no por elemento, así que cada nivel del árbol tiene exactamente dos ramas.

La idea

Un subconjunto es una respuesta de sí o no por cada elemento, así que el árbol de decisión es binario: omitir nums[i], o tomarlo y seguir.

El índice solo avanza, y eso es lo que impide que aparezcan a la vez {1, 2} y {2, 1}. Cada hoja es un conjunto completo de decisiones, así que hay exactamente 2 elevado a la n hojas, y el pop después de la rama de tomar es, otra vez, lo que mantiene correcto el camino compartido.

Ejemplo del mundo real

Elegir qué módulos opcionales activar en una compilación. Cada flag es independiente y el equipo de lanzamientos quiere probar todas las combinaciones: ocho compilaciones para tres flags, dieciséis para cuatro.

El código

Te toca

¿Qué imprime esto?

out = []
subsets([1, 2, 3], 0, [], out)
print(len(out))

Mini quiz

1 / 3

¿Cuántas hojas tiene el árbol de subconjuntos para n elementos?