Saltar al contenido

Subconjuntos con máscara de bits

Fácil#bitmask#subsets~20 min

La misión

Problema

Dada una lista de elementos distintos, devuelve todos sus subconjuntos. Ordena los subconjuntos contando: lee un subconjunto como un número binario en el que el bit i vale 1 cuando items[i] está incluido, y lista los subconjuntos desde el número 0 hasta el mayor. Dentro de cada subconjunto, conserva los elementos en su orden original. La lista tiene como máximo 15 elementos, y la lista vacía también tiene un subconjunto.

Ejemplos

Input:  items = ["a", "b"]
Output: [[], ['a'], ['b'], ['a', 'b']]
Por qué: los números 0, 1, 2 y 3 en binario son 00, 01, 10 y 11
Input:  items = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Por qué: items[2] aparece a partir del número 4, cuando se enciende el bit 2
Input:  items = []
Output: [[]]
Por qué: caso límite: el conjunto vacío es el único subconjunto

Pistas

0 / 3

Tiempo objetivo
O(n · 2ⁿ)
Espacio objetivo
O(n · 2ⁿ)

Restricciones

  • items are distinct
  • 0 ≤ items.length ≤ 15

¿Lo que te frena es la idea y no el código? La máscara de bits como conjunto lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio