Enumeração de Subconjuntos com Máscaras de Bits
Percorra todos os subconjuntos por meio de inteiros.
Enumeração de Subconjuntos com Máscaras de Bits é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Subconjuntos como números
Cada subconjunto de n itens corresponde a um único inteiro. Conte a partir de 0, e os bits de cada número indicarão exatamente quais itens estão incluídos. 🙂
Quantos subconjuntos existem
Um conjunto com n itens tem 2^n subconjuntos. Portanto, percorrer um inteiro de 0 a 2^n menos 1 visita cada subconjunto exatamente uma vez.
for mask in range(1 << n):
pass # mask is one subset1 << n é a contagem
O deslocamento 1 << n é igual a 2 elevado a n. Essa é a forma clara e rápida de escrever o limite superior do laço de subconjuntos.
Leia o bit i
Para verificar se o item i está no subconjunto, teste o bit dele com uma máscara e 1 deslocado para a esquerda em i. Um resultado diferente de zero significa que ele está incluído.
if mask & (1 << i):
take(items[i])Construa a lista escolhida
Percorra cada posição de bit e reúna os itens cujo bit está definido. Assim, uma máscara se transforma no subconjunto concreto que ela representa.
chosen = [items[i] for i in range(n) if mask & (1 << i)]Conjuntos vazio e completo
A máscara 0 representa o subconjunto vazio, e a máscara com todos os bits iguais a 1 representa o conjunto completo. Ambos aparecem naturalmente, pois o laço percorre todos os valores.
Some os elementos de um subconjunto
Dentro do laço, use add para somar os itens escolhidos e avaliar cada subconjunto. Esse é o coração de muitas soluções pequenas de força bruta.
total = sum(v[i] for i in range(n) if mask & (1 << i))Conte os bits definidos
A quantidade de itens escolhidos é igual à quantidade de bits definidos na máscara. Em Python, popcount representa essa quantidade instantaneamente.
size = bin(mask).count("1")Observe o limite
Como existem 2^n subconjuntos, essa técnica só é adequada para valores pequenos de n. Em torno de n igual a 20 fica o limite prático para uma enumeração completa.
Por que as máscaras de bits vencem
Um único laço de inteiros substitui laços aninhados confusos, e as operações com bits são rápidas. O código permanece curto, claro e fácil de testar.
Um padrão reutilizável
Percorra a máscara, decodifique os bits, avalie o subconjunto e acompanhe o melhor resultado. Memorize este modelo e muitos problemas de subconjuntos se tornarão rotineiros.
Verificação rápida
Você quer verificar se o item i está incluído no subconjunto codificado pela máscara.
Recapitulação
Percorra uma máscara de 0 a 2^n menos 1, leia os bits usando a máscara e 1 deslocado para a esquerda e avalie cada subconjunto. É uma força bruta clara para valores pequenos de n. 🚀
Perguntas Frequentes
A aula “Enumeração de Subconjuntos com Máscaras de Bits” é grátis?
Sim — o texto completo de “Enumeração de Subconjuntos com Máscaras de Bits” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Enumeração de Subconjuntos com Máscaras de Bits”?
Percorra todos os subconjuntos por meio de inteiros. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Enumeração de Subconjuntos com Máscaras de Bits”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- A Força Bruta é uma Estratégia Válida
- Enumere com itertools
- Enumeração de Subconjuntos com Máscaras de Bits
- Reduza o Espaço de Busca com Inteligência