Todos os subconjuntos por bitmask
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
Cada item está dentro ou fora de um subconjunto, então n itens dão dois elevado a n subconjuntos. O que mais existe exatamente nessa quantidade?
Os números inteiros de 0 até 2 elevado a n menos 1 são todos os padrões possíveis de n bits, e cada padrão pode descrever um subconjunto.
Percorra os valores de mask de 0 até 2 elevado a n menos 1. Para cada máscara, colete items[i] para todo i cujo bit esteja ligado, o que você pode testar com um deslocamento e um AND.
- Tempo-alvo
- O(n · 2ⁿ)
- Espaço-alvo
- O(n · 2ⁿ)
Restrições
- items are distinct
- 0 ≤ items.length ≤ 15
Solução
Um subconjunto de n itens é uma escolha de sim ou não por item, o que é exatamente um número de n bits; então, contar de 0 até 2 elevado a n menos 1 percorre cada subconjunto uma vez. Para cada número, o bit i é testado com mask >> i & 1, e os itens cujos bits estão ligados formam o subconjunto. Como o bit i sempre significa items[i], os membros ficam na ordem original. O tempo é O(n vezes 2 elevado a n), e o espaço é o mesmo para a saída.
def all_subsets(items):
n, subsets = len(items), []
for mask in range(1 << n): # every n-bit pattern is one subset
subsets.append([items[i] for i in range(n) if mask >> i & 1])
return subsets
print(all_subsets(["a", "b"])) # -> [[], ['a'], ['b'], ['a', 'b']]
print(all_subsets([1, 2, 3])) # -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
print(all_subsets([])) # -> [[]]Travou na ideia, e não no código? Bitmask como conjunto explica isso.