Pular para o conteúdo

Todos os subconjuntos por bitmask

Fácil#bitmask#subsets~20 min

A missão

Problema

Dada uma lista de itens distintos, retorne todos os seus subconjuntos. Ordene os subconjuntos contando: leia um subconjunto como um número binário em que o bit i é 1 quando items[i] está incluído e liste os subconjuntos desse número, de 0 até o maior. Dentro de cada subconjunto, mantenha os itens na ordem original. A lista tem no máximo 15 itens, e a lista vazia ainda tem um subconjunto.

Exemplos

Input:  items = ["a", "b"]
Output: [[], ['a'], ['b'], ['a', 'b']]
Por quê: os números 0, 1, 2 e 3 em binário são 00, 01, 10 e 11
Input:  items = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Por quê: items[2] entra a partir do número 4, quando o bit 2 é ligado
Input:  items = []
Output: [[]]
Por quê: edge case: o conjunto vazio é o único subconjunto

Dicas

0 / 3

Tempo-alvo
O(n · 2ⁿ)
Espaço-alvo
O(n · 2ⁿ)

Restrições

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

Travou na ideia, e não no código? Bitmask como conjunto explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado